<!DOCTYPE html><html><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1"><meta name="sidebardepth" content="6">
<meta name="date" content="2022-02-27 16:12:32">
<meta name="tags" content=""><style>body {
  max-width: 980px;
  border: 1px solid #ddd;
  outline: 1300px solid #fff;
  margin: 16px auto;
}

body .markdown-body
{
  padding: 45px;
}

@font-face {
  font-family: fontawesome-mini;
  src: url(data:font/woff;charset=utf-8;base64,d09GRgABAAAAABE0AA8AAAAAHWwAAQAAAAAAAAAAAAAAAAAAAAAAAAAAAABHU1VCAAABWAAAADsAAABUIIslek9TLzIAAAGUAAAAQwAAAFY3d1HZY21hcAAAAdgAAACqAAACOvWLi0FjdnQgAAAChAAAABMAAAAgBtX/BGZwZ20AAAKYAAAFkAAAC3CKkZBZZ2FzcAAACCgAAAAIAAAACAAAABBnbHlmAAAIMAAABdQAAAjkYT9TNWhlYWQAAA4EAAAAMwAAADYQ6WvNaGhlYQAADjgAAAAfAAAAJAc6A1pobXR4AAAOWAAAACAAAAA0Kmz/7mxvY2EAAA54AAAAHAAAABwQPBJubWF4cAAADpQAAAAgAAAAIAEHC/NuYW1lAAAOtAAAAYQAAALxhQT4h3Bvc3QAABA4AAAAfgAAAMS3SYh9cHJlcAAAELgAAAB6AAAAhuVBK7x4nGNgZGBg4GIwYLBjYHJx8wlh4MtJLMljkGJgYYAAkDwymzEnMz2RgQPGA8qxgGkOIGaDiAIAJjsFSAB4nGNgZHZmnMDAysDAVMW0h4GBoQdCMz5gMGRkAooysDIzYAUBaa4pDA4Pwz+yMwf9z2KIYg5imAYUZgTJAQDcoQvQAHic7ZHNDYJAFIRnBXf94cDRIiyCKkCpwFCPJ092RcKNDoYKcN4+EmMPvpdvk539zQyAPYBCXEUJhBcCrJ5SQ9YLnLJe4qF5rdb+uWPDngNHTkta101pNyWa8lMhn6xx2dqUnW4q9YOIhAOOeueMSgsR/6ry+P7O5s6xVNg4chBsHUuFnWNJ8uZYwrw7chrsHXkODo7cB0dHOYCTY8kv0VE2WJKD6gOlWjsxAAB4nGNgQAMSEMgc9D8LhAESbAPdAHicrVZpd9NGFB15SZyELCULLWphxMRpsEYmbMGACUGyYyBdnK2VoIsUO+m+8Ynf4F/zZNpz6Dd+Wu8bLySQtOdwmpOjd+fN1czbZRJaktgL65GUmy/F1NYmjew8CemGTctRfCg7eyFlisnfBVEQrZbatx2HREQiULWusEQQ+x5ZmmR86FFGy7akV03KLT3pLlvjQb1V334aOsqxO6GkZjN0aD2yJVUYVaJIpj1S0qZlqPorSSu8v8LMV81QwohOImm8GcbQSN4bZ7TKaDW24yiKbLLcKFIkmuFBFHmU1RLn5IoJDMoHzZDyyqcR5cP8iKzYo5xWsEu20/y+L3mndzk/sV9vUbbkQB/Ijuzg7HQlX4RbW2HctJPtKFQRdtd3QmzZ7FT/Zo/ymkYDtysyvdCMYKl8hRArP6HM/iFZLZxP+ZJHo1qykRNB62VO7Es+gdbjiClxzRhZ0N3RCRHU/ZIzDPaYPh788d4plgsTAngcy3pHJZwIEylhczRJ2jByYCVliyqp9a6YOOV1WsRbwn7t2tGXzmjjUHdiPFsPHVs5UcnxaFKnmUyd2knNoykNopR0JnjMrwMoP6JJXm1jNYmVR9M4ZsaERCICLdxLU0EsO7GkKQTNoxm9uRumuXYtWqTJA/Xco/f05la4udNT2g70s0Z/VqdiOtgL0+lp5C/xadrlIkXp+ukZfkziQdYCMpEtNsOUgwdv/Q7Sy9eWHIXXBtju7fMrqH3WRPCkAfsb0B5P1SkJTIWYVYhWQGKta1mWydWsFqnI1HdDmla+rNMEinIcF8e+jHH9XzMzlpgSvt+J07MjLj1z7UsI0xx8m3U9mtepxXIBcWZ5TqdZlu/rNMfyA53mWZ7X6QhLW6ejLD/UaYHlRzodY3lBC5p038GQizDkAg6QMISlA0NYXoIhLBUMYbkIQ1gWYQjLJRjC8mMYwnIZhrC8rGXV1FNJ49qZWAZsQmBijh65zEXlaiq5VEK7aFRqQ54SbpVUFM+qf2WgXjzyhjmwFkiXyJpfMc6Vj0bl+NYVLW8aO1fAsepvH472OfFS1ouFPwX/1dZUJb1izcOTq/Abhp5sJ6o2qXh0TZfPVT26/l9UVFgL9BtIhVgoyrJscGcihI86nYZqoJVDzGzMPLTrdcuan8P9NzFCFlD9+DcUGgvcg05ZSVnt4KzV19uy3DuDcjgTLEkxN/P6VvgiI7PSfpFZyp6PfB5wBYxKZdhqA60VvNknMQ+Z3iTPBHFbUTZI2tjOBIkNHPOAefOdBCZh6qoN5E7hhg34BWFuwXknXKJ6oyyH7kXs8yik/Fun4kT2qGiMwLPZG2Gv70LKb3EMJDT5pX4MVBWhqRg1FdA0Um6oBl/G2bptQsYO9CMqdsOyrOLDxxb3lZJtGYR8pIjVo6Of1l6iTqrcfmYUl++dvgXBIDUxf3vfdHGQyrtayTJHbQNTtxqVU9eaQ+NVh+rmUfW94+wTOWuabronHnpf06rbwcVcLLD2bQ7SUiYX1PVhhQ2iy8WlUOplNEnvuAcYFhjQ71CKjf+r+th8nitVhdFxJN9O1LfR52AM/A/Yf0f1A9D3Y+hyDS7P95oTn2704WyZrqIX66foNzBrrblZugbc0HQD4iFHrY64yg18pwZxeqS5HOkh4GPdFeIBwCaAxeAT3bWM5lMAo/mMOT7A58xh0GQOgy3mMNhmzhrADnMY7DKHwR5zGHzBnHWAL5nDIGQOg4g5DJ4wJwB4yhwGXzGHwdfMYfANc+4DfMscBjFzGCTMYbCv6dYwzC1e0F2gtkFVoANTT1jcw+JQU2XI/o4Xhv29Qcz+wSCm/qjp9pD6Ey8M9WeDmPqLQUz9VdOdIfU3Xhjq7wYx9Q+DmPpMvxjLZQa/jHyXCgeUXWw+5++J9w/bxUC5AAEAAf//AA94nIVVX2hbZRQ/5/t7893s5ja9f7ouzdZ0TTqz3bRJmogbWya6bG6Cq0VbSV2ddIJjFtfIQHEig80Hda8yUN/0YQz8AyriiyD+xQd92R4HCnaCb3samnpumrpsCsLlfPf7zvedc37nL3CAtc/5W/wQZGA3tOBSY/g+TMjHmwzEoM1Q8+ZjRZY4oJhmBw5/YB6Za0yC5AkhlwA1A1yCBIBOwCII0Cj0U8BAMdUCzq05sKwkP7SlUY6fcJk4Fb/RyE79/6P5hjM/F4aZiXBoeMgzcqQ4Xi1hPqfDLG5FT+lchCVU3lYMyvuwhl1mqndQL0RsuloLywHtthLXI06OblTrhfWVnpSJ5+mwu/JdbtuN3IAnkW0LLMcRwaC7ktrlzridM6kVdyf9uO1UNBByI7JhwtG2sEwab07ORBeilWhqavJCqV0qzZTOl/7ZXQ5TbTcdcFelyGhhRDAQpdqp1FEX3w3cFTc1k9pJQkmm4ySCbSikxRP2QOfN+0tHS5MrpQuTU1Mk5nw0E5Xa0WvrOwDyGax9yB9ma6DAg82wHc43SAGTI4GjBWebOePAERFE8/AHaQpZASSTy8A4WwZiLQMQ82mFKATO0ILicRAoDm9p5P99E5b/fXG+kQYY3TYUuqmERWYoT0u/GNYL2q/4WB3LaVS+VynXsVYIcWw6DkCh3nX1D+VzlYN4LClF5yexSQos8exqZ3KVP+wtrC54u4Nznq6cq+xpMpUUnZ8FUYzE86ud0g28NOIv3Gj5/rmA3ABs7S/ywzFuQ4qyd6QxfNtiQIaEgp3w/entQg4Vcbqa16M5FfpeUB8t1+qeg7mI7cUyOe79wOk86gSxkVec4KPTX69++5x68Yubn5/F+w52z7u08sJX7fZXv8ekT/d2mILJxq6sn+SC6qEJknzLJCxyZEKwWVqYmAPBxBE/9DLeZiWHu7lcr/VytrCRuHojncNuTt9h46tmacmYisnSamdN2bZptcsmSysdVsy1PrOvOzF3xN64Rb937t/og9KHxYdcjIUqFAmIAHGHNzlns+RTPgeUYAQm9DwpNxfxbhhBHPaw3/gfTcXO2L+eJVIx5nsyGkvm9X4/f+bGkH45G0PaSjcMXTjcZyTvi3UdHoCDjQd3IDUVsgwYmUoJK/gp4JJxeRI0MKHZIkgynyIBqBTOUs6rOVCojvjZ4mCQz49ZMlMcp8QoYk6NoBfsxnJtsBohpa8iGJS+ZH7gU7NxME6cmF+t7cO9vB8d3jTWSct0ycW9ranXmolNDwmVkNnxe+8JtoztwS5rKJ0xWS95tQ/1zMYzg69MzUZnNtl1ofNbsml/OJm6f9wjRjpnu2o4MzHzn77IQkRd+1DjwMQ2pqSjGMMhyjrgTbBAKksuUm0iU7hI0aN2wOKOq7WYBSH0HGihj/jkiPxAfmwsEbfYrjMG+j3ij932Db/LV7I/xruNrhnroxjR9HRMb2nTvO0ZXOoHPk8H2ZhDPx93qcE/53sH5np/dkIP7zzhTVKdR/BAY/9ElkkR+A6lJGsqpJ4oQcTxpvBT3Kn58VkaJjgHyPEIws57xkaHh9KuVpDEpJZeMbZ5w/zBHi5NMQ4r5VphsFqID7TyB9eR4pX216c3AHxpdAwoqU9qg0ZJ6yVLKmMSz1iG2z27ifx18NkY0LPx1W/wCc2l5LrznrIsiKsqbmB78A9wIGx4tI8rjihVHJyY9pgMirenVq0yWg7Iw7eogG7ZgYM3qR9959A/fZkg6MnD/exlkmc+jWV4SB15XUR+eqC6l6ZmgPtN9z5JMfik05OV8ljylunJ4J+wA/FUaQSSKotsYsCWqaPBidBLcxkWx7XKFRIb45TGaEhjlF9uUVPqXOtcIwsXbBvfoZXIyRYFdkfnqjExH98xpnPczqzjX/uNdO1Y17Wpi5+6Ts8BXtjVFasp9KZ1mOiNbH65c5w6HgmyF2jFCZywM8mWjRc7T5Pmt0lRy7Y71+jYbpGyvwG4sH0XeJxjYGRgYADiwBB/53h+m68M3MwvgCIM1z5N/g6j///9v5H5BbMnkMvBwAQSBQCIcA9gAHicY2BkYGAO+p8FJF/8//v/F/MLBqAICuAFALYQB5kAeJxjfsHAwLwAiCNB+P9fbJjJmoGBMRUo/wKCAfO2EnQAAAAAANoBXgGcAgICVALaA1IDvAPkBAYEPARyAAEAAAANAF0ABAAAAAAAAgAUACQAcwAAAG4LcAAAAAB4nHWRzWrCQBSFT+pPqUIXLXTTzayKUohGKIibCoLuhbrrYtTRxCYZmYyKyz5Fd32HvlDfoO/QkziIFJtw9bvnnpl7ZwLgBt/wcHieGAf2UGd24Atcou+4RH3kuEweO66QXx1XyaHjGh6ROa7jFp/cwStfMVvhy7GHO+/e8QWuvcBxifqz4zL5xXGF/Oa4Sn53XMPE+3Bcx4P3M9DrvYmWoRWNQVN02kFXTPdCU4pSGQu5saE2meiLhU6timPtz3SSs9ypTCdqrJabWJoT5QQnymSRTkXgt0/UkUqVkVbN807ZdtmxdiEWRidi6HqItdErNbN+aO2612qd9sYAGmvsYRBhyUu0EGhQbfK/gzYCdElTOgSdB1eEFBIxFYkNV4RFJWPeZyyYpVQVHTHZx4y/yVGX2LGWFZri51TccUOn5B7nPefVCSPvGhVVwUl9znveO2KkhV8Wk82PZ8qwZf8OVcu1+fSmWCMw/HMOwXvKaysqM+p+cVuWag8tvv+c+xdd+4+teJxtjUEOwiAURJla24KliQfhUA2g/Sl+CKXx+loNrpzVezOLEY34Ron/0WhwQoszOvQYIKFwwQiNSbSBeO2SZ0tBP4j3zVjKNng32ZmtD1VVXCuOiw/pJ8S3WOU6l+K5UOTaDC4+2TjKMtN9KQf1ezLx/Sg/00FCvABHhjDjAAB4nGPw3sFwIihiIyNjX+QGxp0cDBwMyQUbGVidNjEwMmiBGJu5mBg5ICw+BjCLzWkX0wGgNCeQze60i8EBwmZmcNmowtgRGLHBoSNiI3OKy0Y1EG8XRwMDI4tDR3JIBEhJJBBs5mFi5NHawfi/dQNL70YmBhcADHYj9AAA) format('woff');
}

.markdown-body {
  font-family: sans-serif;
  -ms-text-size-adjust: 100%;
  -webkit-text-size-adjust: 100%;
  color: #333333;
  overflow: hidden;
  font-family: "Helvetica Neue", Helvetica, "Segoe UI", Arial, freesans, sans-serif;
  font-size: 16px;
  line-height: 1.6;
  word-wrap: break-word;
}

.markdown-body a {
  background: transparent;
}

.markdown-body a:active,
.markdown-body a:hover {
  outline: 0;
}

.markdown-body b,
.markdown-body strong {
  font-weight: bold;
}

.markdown-body mark {
  background: #ff0;
  color: #000;
  font-style: italic;
  font-weight: bold;
}

.markdown-body sub,
.markdown-body sup {
  font-size: 75%;
  line-height: 0;
  position: relative;
  vertical-align: baseline;
}
.markdown-body sup {
  top: -0.5em;
}
.markdown-body sub {
  bottom: -0.25em;
}

.markdown-body h1 {
  font-size: 2em;
  margin: 0.67em 0;
}

.markdown-body img {
  border: 0;
}

.markdown-body hr {
  -moz-box-sizing: content-box;
  box-sizing: content-box;
  height: 0;
}

.markdown-body pre {
  overflow: auto;
}

.markdown-body code,
.markdown-body kbd,
.markdown-body pre,
.markdown-body samp {
  font-family: monospace, monospace;
  font-size: 1em;
}

.markdown-body input {
  color: inherit;
  font: inherit;
  margin: 0;
}

.markdown-body html input[disabled] {
  cursor: default;
}

.markdown-body input {
  line-height: normal;
}

.markdown-body input[type="checkbox"] {
  box-sizing: border-box;
  padding: 0;
}

.markdown-body table {
  border-collapse: collapse;
  border-spacing: 0;
}

.markdown-body td,
.markdown-body th {
  padding: 0;
}

.markdown-body .codehilitetable,
.markdown-body .highlighttable {
  border: 0;
  border-spacing: 0;
}

.markdown-body .codehilitetable tr,
.markdown-body .highlighttable {
  border: 0;
}

.markdown-body .codehilitetable pre,
.markdown-body .codehilitetable div.codehilite,
.markdown-body .highlighttable pre,
.markdown-body .highlighttable div.highlight {
  margin: 0;
}

.markdown-body .linenos,
.markdown-body .code,
.markdown-body .codehilitetable td,
.markdown-body .highlighttable td {
  border: 0;
  padding: 0;
}

.markdown-body td:not(.linenos) .linenodiv {
  padding: 0 !important;
}

.markdown-body .code {
  width: 100%;
}

.markdown-body .linenos div pre,
.markdown-body .linenodiv pre,
.markdown-body .linenodiv {
  border: 0;
  -webkit-border-radius: 0;
  -moz-border-radius: 0;
  border-radius: 0;
  -webkit-border-top-left-radius: 3px;
  -webkit-border-bottom-left-radius: 3px;
  -moz-border-radius-topleft: 3px;
  -moz-border-radius-bottomleft: 3px;
  border-top-left-radius: 3px;
  border-bottom-left-radius: 3px;
}

.markdown-body .code div pre,
.markdown-body .code div {
  border: 0;
  -webkit-border-radius: 0;
  -moz-border-radius: 0;
  border-radius: 0;
  -webkit-border-top-right-radius: 3px;
  -webkit-border-bottom-right-radius: 3px;
  -moz-border-radius-topright: 3px;
  -moz-border-radius-bottomright: 3px;
  border-top-right-radius: 3px;
  border-bottom-right-radius: 3px;
}

.markdown-body * {
  -moz-box-sizing: border-box;
  box-sizing: border-box;
}

.markdown-body input {
  font: 13px Helvetica, arial, freesans, clean, sans-serif, "Segoe UI Emoji", "Segoe UI Symbol";
  line-height: 1.4;
}

.markdown-body a {
  color: #4183c4;
  text-decoration: none;
}

.markdown-body a:hover,
.markdown-body a:focus,
.markdown-body a:active {
  text-decoration: underline;
}

.markdown-body hr {
  height: 0;
  margin: 15px 0;
  overflow: hidden;
  background: transparent;
  border: 0;
  border-bottom: 1px solid #ddd;
}

.markdown-body hr:before,
.markdown-body hr:after {
  display: table;
  content: " ";
}

.markdown-body hr:after {
  clear: both;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
  margin-top: 15px;
  margin-bottom: 15px;
  line-height: 1.1;
}

.markdown-body h1 {
  font-size: 30px;
}

.markdown-body h2 {
  font-size: 21px;
}

.markdown-body h3 {
  font-size: 16px;
}

.markdown-body h4 {
  font-size: 14px;
}

.markdown-body h5 {
  font-size: 12px;
}

.markdown-body h6 {
  font-size: 11px;
}

.markdown-body blockquote {
  margin: 0;
}

.markdown-body ul,
.markdown-body ol {
  padding: 0;
  margin-top: 0;
  margin-bottom: 0;
}

.markdown-body ol ol,
.markdown-body ul ol {
  list-style-type: lower-roman;
}

.markdown-body ul ul ol,
.markdown-body ul ol ol,
.markdown-body ol ul ol,
.markdown-body ol ol ol {
  list-style-type: lower-alpha;
}

.markdown-body dd {
  margin-left: 0;
}

.markdown-body code,
.markdown-body pre,
.markdown-body samp {
  font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace;
  font-size: 12px;
}

.markdown-body pre {
  margin-top: 0;
  margin-bottom: 0;
}

.markdown-body kbd {
  background-color: #e7e7e7;
  background-image: -moz-linear-gradient(#fefefe, #e7e7e7);
  background-image: -webkit-linear-gradient(#fefefe, #e7e7e7);
  background-image: linear-gradient(#fefefe, #e7e7e7);
  background-repeat: repeat-x;
  border-radius: 2px;
  border: 1px solid #cfcfcf;
  color: #000;
  padding: 3px 5px;
  line-height: 10px;
  font: 11px Consolas, "Liberation Mono", Menlo, Courier, monospace;
  display: inline-block;
}

.markdown-body>*:first-child {
  margin-top: 0 !important;
}

.markdown-body>*:last-child {
  margin-bottom: 0 !important;
}

.markdown-body .headerlink {
  font: normal 400 16px fontawesome-mini;
  vertical-align: middle;
  margin-left: -16px;
  float: left;
  display: inline-block;
  text-decoration: none;
  opacity: 0;
  color: #333;
}

.markdown-body .headerlink:focus {
  outline: none;
}

.markdown-body h1 .headerlink {
  margin-top: 0.8rem;
}

.markdown-body h2 .headerlink,
.markdown-body h3 .headerlink {
  margin-top: 0.6rem;
}

.markdown-body h4 .headerlink {
  margin-top: 0.2rem;
}

.markdown-body h5 .headerlink,
.markdown-body h6 .headerlink {
  margin-top: 0;
}

.markdown-body .headerlink:hover,
.markdown-body h1:hover .headerlink,
.markdown-body h2:hover .headerlink,
.markdown-body h3:hover .headerlink,
.markdown-body h4:hover .headerlink,
.markdown-body h5:hover .headerlink,
.markdown-body h6:hover .headerlink {
  opacity: 1;
  text-decoration: none;
}

.markdown-body h1 {
  padding-bottom: 0.3em;
  font-size: 2.25em;
  line-height: 1.2;
  border-bottom: 1px solid #eee;
}

.markdown-body h2 {
  padding-bottom: 0.3em;
  font-size: 1.75em;
  line-height: 1.225;
  border-bottom: 1px solid #eee;
}

.markdown-body h3 {
  font-size: 1.5em;
  line-height: 1.43;
}

.markdown-body h4 {
  font-size: 1.25em;
}

.markdown-body h5 {
  font-size: 1em;
}

.markdown-body h6 {
  font-size: 1em;
  color: #777;
}

.markdown-body p,
.markdown-body blockquote,
.markdown-body ul,
.markdown-body ol,
.markdown-body dl,
.markdown-body table,
.markdown-body pre,
.markdown-body .admonition {
  margin-top: 0;
  margin-bottom: 16px;
}

.markdown-body hr {
  height: 4px;
  padding: 0;
  margin: 16px 0;
  background-color: #e7e7e7;
  border: 0 none;
}

.markdown-body ul,
.markdown-body ol {
  padding-left: 2em;
}

.markdown-body ul ul,
.markdown-body ul ol,
.markdown-body ol ol,
.markdown-body ol ul {
  margin-top: 0;
  margin-bottom: 0;
}

.markdown-body li>p {
  margin-top: 16px;
}

.markdown-body dl {
  padding: 0;
}

.markdown-body dl dt {
  padding: 0;
  margin-top: 16px;
  font-size: 1em;
  font-style: italic;
  font-weight: bold;
}

.markdown-body dl dd {
  padding: 0 16px;
  margin-bottom: 16px;
}

.markdown-body blockquote {
  padding: 0 15px;
  color: #777;
  border-left: 4px solid #ddd;
}

.markdown-body blockquote>:first-child {
  margin-top: 0;
}

.markdown-body blockquote>:last-child {
  margin-bottom: 0;
}

.markdown-body table {
  display: block;
  width: 100%;
  overflow: auto;
  word-break: normal;
  word-break: keep-all;
}

.markdown-body table th {
  font-weight: bold;
}

.markdown-body table th,
.markdown-body table td {
  padding: 6px 13px;
  border: 1px solid #ddd;
}

.markdown-body table tr {
  background-color: #fff;
  border-top: 1px solid #ccc;
}

.markdown-body table tr:nth-child(2n) {
  background-color: #f8f8f8;
}

.markdown-body img {
  max-width: 100%;
  -moz-box-sizing: border-box;
  box-sizing: border-box;
}

.markdown-body code,
.markdown-body samp {
  padding: 0;
  padding-top: 0.2em;
  padding-bottom: 0.2em;
  margin: 0;
  font-size: 85%;
  background-color: rgba(0,0,0,0.04);
  border-radius: 3px;
}

.markdown-body code:before,
.markdown-body code:after {
  letter-spacing: -0.2em;
  content: "\00a0";
}

.markdown-body pre>code {
  padding: 0;
  margin: 0;
  font-size: 100%;
  word-break: normal;
  white-space: pre;
  background: transparent;
  border: 0;
}

.markdown-body .codehilite,
.markdown-body .highlight {
  margin-bottom: 16px;
}

.markdown-body .codehilite pre,
.markdown-body .highlight pre,
.markdown-body pre {
  padding: 16px;
  overflow: auto;
  font-size: 85%;
  line-height: 1.45;
  background-color: #f7f7f7;
  border-radius: 3px;
}

.markdown-body .codehilite pre,
.markdown-body .highlight pre {
  margin-bottom: 0;
  word-break: normal;
}

.markdown-body pre {
  word-wrap: normal;
}

.markdown-body pre code {
  display: inline;
  max-width: initial;
  padding: 0;
  margin: 0;
  overflow: initial;
  line-height: inherit;
  word-wrap: normal;
  background-color: transparent;
  border: 0;
}

.markdown-body pre code:before,
.markdown-body pre code:after {
  content: normal;
}

/* Admonition */
.markdown-body .admonition {
  -webkit-border-radius: 3px;
  -moz-border-radius: 3px;
  position: relative;
  border-radius: 3px;
  border: 1px solid #e0e0e0;
  border-left: 6px solid #333;
  padding: 10px 10px 10px 30px;
}

.markdown-body .admonition table {
  color: #333;
}

.markdown-body .admonition p {
  padding: 0;
}

.markdown-body .admonition-title {
  font-weight: bold;
  margin: 0;
}

.markdown-body .admonition>.admonition-title {
  color: #333;
}

.markdown-body .attention>.admonition-title {
  color: #a6d796;
}

.markdown-body .caution>.admonition-title {
  color: #d7a796;
}

.markdown-body .hint>.admonition-title {
  color: #96c6d7;
}

.markdown-body .danger>.admonition-title {
  color: #c25f77;
}

.markdown-body .question>.admonition-title {
  color: #96a6d7;
}

.markdown-body .note>.admonition-title {
  color: #d7c896;
}

.markdown-body .admonition:before,
.markdown-body .attention:before,
.markdown-body .caution:before,
.markdown-body .hint:before,
.markdown-body .danger:before,
.markdown-body .question:before,
.markdown-body .note:before {
  font: normal normal 16px fontawesome-mini;
  -moz-osx-font-smoothing: grayscale;
  -webkit-user-select: none;
  -moz-user-select: none;
  -ms-user-select: none;
  user-select: none;
  line-height: 1.5;
  color: #333;
  position: absolute;
  left: 0;
  top: 0;
  padding-top: 10px;
  padding-left: 10px;
}

.markdown-body .admonition:before {
  content: "\f056\00a0";
  color: 333;
}

.markdown-body .attention:before {
  content: "\f058\00a0";
  color: #a6d796;
}

.markdown-body .caution:before {
  content: "\f06a\00a0";
  color: #d7a796;
}

.markdown-body .hint:before {
  content: "\f05a\00a0";
  color: #96c6d7;
}

.markdown-body .danger:before {
  content: "\f057\00a0";
  color: #c25f77;
}

.markdown-body .question:before {
  content: "\f059\00a0";
  color: #96a6d7;
}

.markdown-body .note:before {
  content: "\f040\00a0";
  color: #d7c896;
}

.markdown-body .admonition::after {
  content: normal;
}

.markdown-body .attention {
  border-left: 6px solid #a6d796;
}

.markdown-body .caution {
  border-left: 6px solid #d7a796;
}

.markdown-body .hint {
  border-left: 6px solid #96c6d7;
}

.markdown-body .danger {
  border-left: 6px solid #c25f77;
}

.markdown-body .question {
  border-left: 6px solid #96a6d7;
}

.markdown-body .note {
  border-left: 6px solid #d7c896;
}

.markdown-body .admonition>*:first-child {
  margin-top: 0 !important;
}

.markdown-body .admonition>*:last-child {
  margin-bottom: 0 !important;
}

/* progress bar*/
.markdown-body .progress {
  display: block;
  width: 300px;
  margin: 10px 0;
  height: 24px;
  -webkit-border-radius: 3px;
  -moz-border-radius: 3px;
  border-radius: 3px;
  background-color: #ededed;
  position: relative;
  box-shadow: inset -1px 1px 3px rgba(0, 0, 0, .1);
}

.markdown-body .progress-label {
  position: absolute;
  text-align: center;
  font-weight: bold;
  width: 100%; margin: 0;
  line-height: 24px;
  color: #333;
  text-shadow: 1px 1px 0 #fefefe, -1px -1px 0 #fefefe, -1px 1px 0 #fefefe, 1px -1px 0 #fefefe, 0 1px 0 #fefefe, 0 -1px 0 #fefefe, 1px 0 0 #fefefe, -1px 0 0 #fefefe, 1px 1px 2px #000;
  -webkit-font-smoothing: antialiased !important;
  white-space: nowrap;
  overflow: hidden;
}

.markdown-body .progress-bar {
  height: 24px;
  float: left;
  -webkit-border-radius: 3px;
  -moz-border-radius: 3px;
  border-radius: 3px;
  background-color: #96c6d7;
  box-shadow: inset 0 1px 0 rgba(255, 255, 255, .5), inset 0 -1px 0 rgba(0, 0, 0, .1);
  background-size: 30px 30px;
  background-image: -webkit-linear-gradient(
    135deg, rgba(255, 255, 255, .4) 27%,
    transparent 27%,
    transparent 52%, rgba(255, 255, 255, .4) 52%,
    rgba(255, 255, 255, .4) 77%,
    transparent 77%, transparent
  );
  background-image: -moz-linear-gradient(
    135deg,
    rgba(255, 255, 255, .4) 27%, transparent 27%,
    transparent 52%, rgba(255, 255, 255, .4) 52%,
    rgba(255, 255, 255, .4) 77%, transparent 77%,
    transparent
  );
  background-image: -ms-linear-gradient(
    135deg,
    rgba(255, 255, 255, .4) 27%, transparent 27%,
    transparent 52%, rgba(255, 255, 255, .4) 52%,
    rgba(255, 255, 255, .4) 77%, transparent 77%,
    transparent
  );
  background-image: -o-linear-gradient(
    135deg,
    rgba(255, 255, 255, .4) 27%, transparent 27%,
    transparent 52%, rgba(255, 255, 255, .4) 52%,
    rgba(255, 255, 255, .4) 77%, transparent 77%,
    transparent
  );
  background-image: linear-gradient(
    135deg,
    rgba(255, 255, 255, .4) 27%, transparent 27%,
    transparent 52%, rgba(255, 255, 255, .4) 52%,
    rgba(255, 255, 255, .4) 77%, transparent 77%,
    transparent
  );
}

.markdown-body .progress-100plus .progress-bar {
  background-color: #a6d796;
}

.markdown-body .progress-80plus .progress-bar {
  background-color: #c6d796;
}

.markdown-body .progress-60plus .progress-bar {
  background-color: #d7c896;
}

.markdown-body .progress-40plus .progress-bar {
  background-color: #d7a796;
}

.markdown-body .progress-20plus .progress-bar {
  background-color: #d796a6;
}

.markdown-body .progress-0plus .progress-bar {
  background-color: #c25f77;
}

.markdown-body .candystripe-animate .progress-bar{
  -webkit-animation: animate-stripes 3s linear infinite;
  -moz-animation: animate-stripes 3s linear infinite;
  animation: animate-stripes 3s linear infinite;
}

@-webkit-keyframes animate-stripes {
  0% {
    background-position: 0 0;
  }

  100% {
    background-position: 60px 0;
  }
}

@-moz-keyframes animate-stripes {
  0% {
    background-position: 0 0;
  }

  100% {
    background-position: 60px 0;
  }
}

@keyframes animate-stripes {
  0% {
    background-position: 0 0;
  }

  100% {
    background-position: 60px 0;
  }
}

.markdown-body .gloss .progress-bar {
  box-shadow:
    inset 0 4px 12px rgba(255, 255, 255, .7),
    inset 0 -12px 0 rgba(0, 0, 0, .05);
}

/* MultiMarkdown Critic Blocks */
.markdown-body .critic_mark {
  background: #ff0;
}

.markdown-body .critic_delete {
  color: #c82829;
  text-decoration: line-through;
}

.markdown-body .critic_insert {
  color: #718c00 ;
  text-decoration: underline;
}

.markdown-body .critic_comment {
  color: #8e908c;
  font-style: italic;
}

.markdown-body .headeranchor {
  font: normal normal 16px fontawesome-mini;
  line-height: 1;
  display: inline-block;
  text-decoration: none;
  -webkit-font-smoothing: antialiased;
  -moz-osx-font-smoothing: grayscale;
  -webkit-user-select: none;
  -moz-user-select: none;
  -ms-user-select: none;
  user-select: none;
}

.headeranchor:before {
  content: '\e157';
}

.markdown-body .task-list-item {
  list-style-type: none;
}

.markdown-body .task-list-item+.task-list-item {
  margin-top: 3px;
}

.markdown-body .task-list-item input {
  margin: 0 4px 0.25em -20px;
  vertical-align: middle;
}

/* Media */
@media only screen and (min-width: 480px) {
  .markdown-body {
    font-size:14px;
  }
}

@media only screen and (min-width: 768px) {
  .markdown-body {
    font-size:16px;
  }
}

@media print {
  .markdown-body * {
    background: transparent !important;
    color: black !important;
    filter:none !important;
    -ms-filter: none !important;
  }

  .markdown-body {
    font-size:12pt;
    max-width:100%;
    outline:none;
    border: 0;
  }

  .markdown-body a,
  .markdown-body a:visited {
    text-decoration: underline;
  }

  .markdown-body .headeranchor-link {
    display: none;
  }

  .markdown-body a[href]:after {
    content: " (" attr(href) ")";
  }

  .markdown-body abbr[title]:after {
    content: " (" attr(title) ")";
  }

  .markdown-body .ir a:after,
  .markdown-body a[href^="javascript:"]:after,
  .markdown-body a[href^="#"]:after {
    content: "";
  }

  .markdown-body pre {
    white-space: pre;
    white-space: pre-wrap;
    word-wrap: break-word;
  }

  .markdown-body pre,
  .markdown-body blockquote {
    border: 1px solid #999;
    padding-right: 1em;
    page-break-inside: avoid;
  }

  .markdown-body .progress,
  .markdown-body .progress-bar {
    -moz-box-shadow: none;
    -webkit-box-shadow: none;
    box-shadow: none;
  }

  .markdown-body .progress {
    border: 1px solid #ddd;
  }

  .markdown-body .progress-bar {
    height: 22px;
    border-right: 1px solid #ddd;
  }

  .markdown-body tr,
  .markdown-body img {
    page-break-inside: avoid;
  }

  .markdown-body img {
    max-width: 100% !important;
  }

  .markdown-body p,
  .markdown-body h2,
  .markdown-body h3 {
    orphans: 3;
    widows: 3;
  }

  .markdown-body h2,
  .markdown-body h3 {
    page-break-after: avoid;
  }
}
</style><style>/*GitHub*/
.highlight {background-color:#fff;color:#333333;}
.highlight .hll {background-color:#ffffcc;}
.highlight .c{color:#999988;font-style:italic}
.highlight .err{color:#a61717;background-color:#e3d2d2}
.highlight .k{font-weight:bold}
.highlight .o{font-weight:bold}
.highlight .cm{color:#999988;font-style:italic}
.highlight .cp{color:#999999;font-weight:bold}
.highlight .c1{color:#999988;font-style:italic}
.highlight .cs{color:#999999;font-weight:bold;font-style:italic}
.highlight .gd{color:#000000;background-color:#ffdddd}
.highlight .ge{font-style:italic}
.highlight .gr{color:#aa0000}
.highlight .gh{color:#999999}
.highlight .gi{color:#000000;background-color:#ddffdd}
.highlight .go{color:#888888}
.highlight .gp{color:#555555}
.highlight .gs{font-weight:bold}
.highlight .gu{color:#800080;font-weight:bold}
.highlight .gt{color:#aa0000}
.highlight .kc{font-weight:bold}
.highlight .kd{font-weight:bold}
.highlight .kn{font-weight:bold}
.highlight .kp{font-weight:bold}
.highlight .kr{font-weight:bold}
.highlight .kt{color:#445588;font-weight:bold}
.highlight .m{color:#009999}
.highlight .s{color:#dd1144}
.highlight .n{color:#333333}
.highlight .na{color:teal}
.highlight .nb{color:#0086b3}
.highlight .nc{color:#445588;font-weight:bold}
.highlight .no{color:teal}
.highlight .ni{color:purple}
.highlight .ne{color:#990000;font-weight:bold}
.highlight .nf{color:#990000;font-weight:bold}
.highlight .nn{color:#555555}
.highlight .nt{color:navy}
.highlight .nv{color:teal}
.highlight .ow{font-weight:bold}
.highlight .w{color:#bbbbbb}
.highlight .mf{color:#009999}
.highlight .mh{color:#009999}
.highlight .mi{color:#009999}
.highlight .mo{color:#009999}
.highlight .sb{color:#dd1144}
.highlight .sc{color:#dd1144}
.highlight .sd{color:#dd1144}
.highlight .s2{color:#dd1144}
.highlight .se{color:#dd1144}
.highlight .sh{color:#dd1144}
.highlight .si{color:#dd1144}
.highlight .sx{color:#dd1144}
.highlight .sr{color:#009926}
.highlight .s1{color:#dd1144}
.highlight .ss{color:#990073}
.highlight .bp{color:#999999}
.highlight .vc{color:teal}
.highlight .vg{color:teal}
.highlight .vi{color:teal}
.highlight .il{color:#009999}
.highlight .gc{color:#999;background-color:#EAF2F5}
</style><title>背包问题</title></head><body><article class="markdown-body"><h2 id="-">- 动态规划<a class="headerlink" href="#-" title="Permanent link"></a></h2>
<h2 id="_1">索引<a class="headerlink" href="#_1" title="Permanent link"></a></h2>
<ol>
<li>
<p><a href="#一、01背包问题">01背包问题</a></p>
</li>
<li>
<p><a href="#二、完全背包问题">完全背包问题</a></p>
</li>
<li>
<p><a href="#三、多重背包问题">多重背包问题</a></p>
</li>
<li>
<p><a href="#四、混合三种背包问题">混合三种背包问题</a></p>
</li>
<li>
<p><a href="#五、二维费用的背包问题">二维费用的背包问题</a></p>
</li>
<li>
<p><a href="#六、分组的背包问题">分组的背包问题</a></p>
</li>
<li>
<p><a href="#七、有依赖的背包问题">有依赖的背包问题</a></p>
</li>
<li>
<p><a href="#八、泛化物品">泛化物品</a></p>
</li>
<li>
<p><a href="#九、背包问题问法的变化">背包问题问法的变化</a></p>
</li>
</ol>
<h2 id="_2">相关资源<a class="headerlink" href="#_2" title="Permanent link"></a></h2>
<p>参考视频: <a href="https://www.bilibili.com/video/av91941737">听懂不翻车系列之 &ndash; 背包问题（01 背包 完全背包 多重背包 二维费用背包）</a></p>
<p>知乎: <a href="https://zhuanlan.zhihu.com/p/139368825">dd 大牛的《背包九讲》</a></p>
<p>博客园: <a href="https://www.cnblogs.com/coded-ream/p/7208019.html">背包问题（背包九讲）</a></p>
<h2 id="01">一、01背包问题<a class="headerlink" href="#01" title="Permanent link"></a></h2>
<h3 id="_3">题目描述<a class="headerlink" href="#_3" title="Permanent link"></a></h3>
<p>有一个最多能装容量 M 的背包，现在有 n 件物品，他们所占容量分别是 W1, W2, W3, &hellip;, Wn，他们的价值的是，C1, C2, C3, &hellip;, Cn，假定所有的物品重量和价格都是非负的，且限定每种物品只能选择0个或1个，求能获得的最大价值。</p>
<h3 id="_4">特点<a class="headerlink" href="#_4" title="Permanent link"></a></h3>
<p>每个物品只能选择一次</p>
<h3 id="_5">思路<a class="headerlink" href="#_5" title="Permanent link"></a></h3>
<h4 id="_6">思路一<a class="headerlink" href="#_6" title="Permanent link"></a></h4>
<h5 id="_7">分析<a class="headerlink" href="#_7" title="Permanent link"></a></h5>
<blockquote>
<p>使用一个二维数组 <code>dp[i][j]</code></p>
<p>（注：dp 即 Dynamic Programming，动态算法）</p>
<p>其中 <code>i</code> 表示当前只能拿到前 <code>i</code> 件物品，</p>
<p><code>j</code> 表示假定背包容量，</p>
<p><code>dp[i][j]</code> 表示容量为 <code>j</code> 的背包，只能拿前 <code>i</code> 件物品时能获得的的最大价值。</p>
<blockquote>
<p>已知，<code>i</code> 最大值为条件的物品数 <code>n</code></p>
</blockquote>
<p>并将 <code>n</code> 件物品的所占容量与价值分别放在 <code>w[i]</code>, <code>c[i]</code> 数组，表示第 <code>i</code> 件物品所占容量和价值。</p>
<blockquote>
<p>一般，算法中间会常出现 <code>i-1</code> 位置的访问，所以 <code>i</code> 从 1 开始。</p>
</blockquote>
</blockquote>
<p>从 <code>i=1,j=0</code>，先 <code>j</code> 后 <code>i</code> 的顺序一次计算最大价值，（类似遍历，外层为 <code>i</code>，内层为 <code>j</code>）</p>
<p>当算到 <code>i+1</code> 时，两种情况，背包容量 <code>j</code></p>
<blockquote>
<p>注：这里使用 <code>i+1</code> 是为了表示前面 <code>i</code> 已经算过了，往后计算到 <code>i+1</code> 时的能获得的最大价值。</p>
<p>实际程序中肯定是一个确定的数字，而不是 <code>i+1</code> 的形式。</p>
<p>对 <code>i+1</code> 为1，即刚开始算，<code>i</code> 就是 0，0件物品，最大价值0，对 <code>dp[0][...]</code> 全初始化为0</p>
</blockquote>
<ul>
<li>拿不起第 <code>i+1</code> 件物品 (<code>j &lt; w[i+1]</code>)</li>
</ul>
<p>能获得的最大价值与只能拿前 <code>i</code> 件物品时相同 (<code>=dp[i][j]</code>)。</p>
<ul>
<li>拿得起第 <code>i+1</code> 件物品 (<code>j ≥ w[i+1]</code>)</li>
</ul>
<p>又分两种情况</p>
<ul>
<li>
<p>不拿</p>
<p>能获得的最大价值与只能拿前 <code>i</code> 件物品时相同 (<code>=dp[i][j]</code>)</p>
</li>
<li>
<p>拿</p>
<p>此时能获得的最大价值为 拿走后只能拿前 <code>i</code> 件物品，背包容量为 <code>j-w[i]</code> 能获得的最大价值 <code>dp[i][j-w[i]]</code>，加上当前第 <code>i+1</code> 件物品的价值 <code>c[i]</code>，即 <code>dp[i][j-w[i]]+c[i]</code></p>
</li>
</ul>
<p>比较二者价值，取最大值。</p>
<p>这样一直算到 <code>dp[i][j]</code> 的值，就是最终的能获得的最大价值。</p>
<p>参考代码：</p>
<blockquote>
<p>（用的不是 <code>i+1</code>, 而是 <code>i</code>，更符合实际）</p>
</blockquote>
<div class="highlight"><pre><span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">&lt;</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
  <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">j</span><span class="o">]=</span><span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="o">][</span><span class="n">j</span><span class="o">];</span>
<span class="o">}</span> <span class="k">else</span> <span class="o">{</span>
  <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="o">][</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="o">][</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
<span class="o">}</span>
</pre></div>

<h5 id="_8">参考代码<a class="headerlink" href="#_8" title="Permanent link"></a></h5>
<div class="highlight"><pre><span class="kn">package</span> <span class="nn">sing</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.*</span><span class="o">;</span>

<span class="cm">/**</span>
<span class="cm"> * @author xing</span>
<span class="cm"> * @date 2022/2/27 14:09</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Main</span> <span class="o">{</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Scanner</span> <span class="n">sc</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Scanner</span><span class="o">(</span><span class="n">System</span><span class="o">.</span><span class="na">in</span><span class="o">);</span>
        <span class="kt">int</span> <span class="n">capacity</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="c1">// 创建 dp 数组, dp[物品数+1][背包容量+1]</span>
        <span class="c1">// 物品数+1 是为了空出开始的0，方便后边的使用 i-1 索引操作</span>
        <span class="c1">// 背包容量+1 是为了空出开始的0，方便后边遍历时使用 for 里的 j 作为数组索引时又能够表示背包容量（从1到最大背包容量），方便与给的物品所占容量比较。</span>
        <span class="n">Integer</span><span class="o">[][]</span> <span class="n">dp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">][</span><span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="c1">// 0个物品时全赋值为0，防止后边用到时报空指针异常</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
            <span class="n">dp</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="n">j</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
        <span class="o">}</span>
        <span class="c1">// 背包容量为0时也全赋为0，防止后边用到时报空指针异常</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="mi">0</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
        <span class="o">}</span>

        <span class="c1">// 创建 w[], c[], 保存物品的容量与价值，长度与前面一致</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">w</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">c</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="c1">// 索引为0处设置为0，后边索引都是1开始，所以没必要</span>
        <span class="c1">// w[0]=0;</span>
        <span class="c1">// c[0]=0;</span>

        <span class="c1">// 遍历获取物品信息，从 1 开始</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="c1">// 所占容量</span>
            <span class="kt">int</span> <span class="n">volumn</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
            <span class="c1">// 价值</span>
            <span class="kt">int</span> <span class="n">value</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
            <span class="c1">// 放入数组</span>
            <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]=</span><span class="n">volumn</span><span class="o">;</span>
            <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]=</span><span class="n">value</span><span class="o">;</span>
        <span class="o">}</span>

        <span class="c1">// 遍历物品数量</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="c1">// 遍历背包容量</span>
            <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
                <span class="c1">// 背包容量小于所占容量，拿不下</span>
                <span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">&lt;</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
                    <span class="c1">// 等于只能拿前 i-1 件物品时能获得的最大价值</span>
                    <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">j</span><span class="o">]=</span><span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="o">][</span><span class="n">j</span><span class="o">];</span>
                <span class="o">}</span>
                <span class="c1">// 背包容量大于等于所占容量，能拿下</span>
                <span class="k">else</span> <span class="o">{</span>
                    <span class="c1">// 不拿</span>
                    <span class="c1">// 等于只能拿前 i-1 件物品时能获得的最大价值</span>
                    <span class="kt">int</span> <span class="n">valuePut</span> <span class="o">=</span> <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="o">][</span><span class="n">j</span><span class="o">];</span>
                    <span class="c1">// 拿</span>
                    <span class="c1">// 当前物品价值 + 剩下物品与容量能获得的最大价值</span>
                    <span class="kt">int</span> <span class="n">valueNotPut</span> <span class="o">=</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="o">][</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]];</span>
                    <span class="c1">// 放入最大值</span>
                    <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">valuePut</span><span class="o">,</span> <span class="n">valueNotPut</span><span class="o">);</span>
                <span class="o">}</span>
            <span class="o">}</span>
        <span class="o">}</span>
        <span class="c1">// 打印最后结果，注意与创建时表示长度的 dp[n+1][capacity+1] 区分开，不要写错</span>
        <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">n</span><span class="o">][</span><span class="n">capacity</span><span class="o">]);</span>
        <span class="c1">// 打印 dp 表</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
                <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">print</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="n">j</span><span class="o">]+</span><span class="s">&quot; &quot;</span><span class="o">);</span>
            <span class="o">}</span>
            <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">();</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>输入：</p>
<p>```:no-line-numbers
10 4
2 1
3 3
4 5
7 9
<div class="highlight"><pre>很明显可以知道，一开始背包容量为1时，放不下，就要往上找，那么就用到前面的 `dp[i-1][1]` 也就是 `dp[0][1]`，而背包容量与物品所占相同时，`j-w[i]` 就是 0，就用到了 `dp[..][0]`，前面一开始的初始化就有了部分的意义（一部分可能就用不到）。

输出结果:

```:no-line-numbers
12
0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 1 1 1 
0 0 1 3 3 4 4 4 4 4 4 
0 0 1 3 5 5 6 8 8 9 9 
0 0 1 3 5 5 6 9 9 10 12 
</pre></div></p>
<p>第一行以及第一列是赋的0，第二列就是计算的0了。1个背包容量啥也放不下。</p>
<h4 id="_9">思路二（优化）<a class="headerlink" href="#_9" title="Permanent link"></a></h4>
<h5 id="_10">优化内容<a class="headerlink" href="#_10" title="Permanent link"></a></h5>
<ul>
<li>降低 <code>dp</code> 数组维度</li>
</ul>
<p>根据动态规划的后无效性原则，当前状态只跟上一个状态有关。</p>
<p>那么我们可以通过压缩的方式，或者说滚动数组，</p>
<p>只使用一维数组来实现，每次循环不断的更新数组</p>
<h5 id="_11">分析<a class="headerlink" href="#_11" title="Permanent link"></a></h5>
<p>原来二维是物品数量，和背包容量，</p>
<p>现在变为一维，这个一维长度使用什么，物品数量，背包容量，还是其他。</p>
<p>考虑前面的代码，两层循环，外层是 <code>i</code>，内层是 <code>j</code>。</p>
<p><code>i</code> 变化一次，就要算一遍 <code>j</code>，</p>
<p>外边变化一次，里边更新一遍</p>
<p>那我们为什么不将背包容量 <code>j</code> 这一层的数组提出来，作为一维数组。</p>
<p>然后 <code>i</code> 每变化一次。</p>
<p>这个一维数组变化前，就是旧的，上一层得到的数据。</p>
<p>用这个数据来更新，得到第 <code>i</code> 个物品的对背包容量的一位数组。</p>
<p>所以数组定义是</p>
<p><code>Integer[] dp = new Integer[capacity+1]</code></p>
<p>那么，按照前面的思维，对第 <code>i</code> 件物品，拿与不拿</p>
<ul>
<li>拿不了</li>
</ul>
<p>应该是 <code>dp[i-1][j]</code>，也就是 <code>dp[j]</code>。</p>
<p>注意这里的 <code>dp[j]</code> 的数组 <code>dp</code> 应该是上个循环得到的原封不动的数组。才是 <code>[i-1]</code>。</p>
<ul>
<li>
<p>拿得了</p>
</li>
<li>
<p>不拿</p>
<p>还是 <code>dp[i-1][j]</code>，也就是 <code>dp[j]</code>。</p>
</li>
<li>
<p>拿</p>
<p>应该是 <code>Math.max(dp[i-1][j], c[i]+dp[i-1][j-w[i]])</code></p>
<p>到一维数组应该是 <code>Math.max(dp[j], c[i]+dp[j-w[i]])</code></p>
</li>
</ul>
<p>因为没有了 <code>i</code> 的那一层，那原来的 拿不了 与 拿得了不拿的等式 <code>dp[i][j]=dp[i-1][j]</code>，都变为了 <code>dp[j]=dp[j]</code>，可以省略不写了</p>
<p>所以这部分代码就可以简化为</p>
<div class="highlight"><pre><span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
  <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]));</span>
<span class="o">}</span>
</pre></div>

<p>或者</p>
<div class="highlight"><pre>  <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">?</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">:</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
</pre></div>

<blockquote>
<p>注意，下边代码不好</p>
<div class="highlight"><pre><span class="kt">int</span> <span class="n">valuePut</span> <span class="o">=</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]];</span>
<span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">&amp;</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">&lt;</span> <span class="n">valuePut</span><span class="o">)</span> <span class="o">{</span>
  <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">valuePut</span><span class="o">;</span>
<span class="o">}</span>
</pre></div>

<p>因为上边的数组索引 <code>[j-w[i]]</code> 违反了下边的条件 <code>j &gt;= w[i]</code>，</p>
<p>可以预见的是，如果不满足 <code>j &gt;= w[i]</code>，上边的代码会报错。</p>
</blockquote>
<p>代码中用到的 <code>dp[j]</code> 和 <code>dp[j-w[i]]</code> 代表数组中每个值都有可能被访问到，所以我们对 <code>dp</code> 数组进行整个的初始化。</p>
<p>因为背包为0时，最大价值肯定为0，所以下边的 关于 <code>j</code> 的 <code>for</code> 循环的遍历，我们还是不用去算到 0，只需要将 <code>dp[0]</code> 初始化为0就不用管了。</p>
<p>对于其他位置的初始化的细节，请看再往下的 <a href="#一维dp数组初始化的细节问题">一维dp数组初始化的细节问题</a></p>
<h5 id="_12">参考代码一（错误）<a class="headerlink" href="#_12" title="Permanent link"></a></h5>
<div class="highlight"><pre><span class="kn">package</span> <span class="nn">sing</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.*</span><span class="o">;</span>

<span class="cm">/**</span>
<span class="cm"> * @author xing</span>
<span class="cm"> * @date 2022/2/27 14:09</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Main</span> <span class="o">{</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Scanner</span> <span class="n">sc</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Scanner</span><span class="o">(</span><span class="n">System</span><span class="o">.</span><span class="na">in</span><span class="o">);</span>
        <span class="kt">int</span> <span class="n">capacity</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="c1">// 创建 dp 数组, dp[容量+1]</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">dp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="c1">// 初始化数组</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
        <span class="o">}</span>

        <span class="c1">// 创建 w[], c[]</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">w</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">c</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="c1">// 索引为0处设置为0，后边索引都是1开始，所以没必要</span>
        <span class="c1">// w[0]=0;</span>
        <span class="c1">// c[0]=0;</span>

        <span class="c1">// 遍历获取物品信息，从 1 开始，赋值给数组</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="c1">// 所占容量</span>
            <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
            <span class="c1">// 价值</span>
            <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="o">}</span>

        <span class="c1">// 遍历物品数量</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="c1">// 遍历背包容量</span>
            <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
                <span class="c1">// 背包容量大于等于所占容量</span>
                <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]){</span>
                    <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
                <span class="o">}</span>
            <span class="o">}</span>
            <span class="c1">// 输出dp表</span>
            <span class="k">for</span> <span class="o">(</span><span class="n">Integer</span> <span class="n">integer</span> <span class="o">:</span> <span class="n">dp</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">print</span><span class="o">(</span><span class="n">integer</span> <span class="o">+</span> <span class="s">&quot; &quot;</span><span class="o">);</span>
            <span class="o">}</span>
            <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">();</span>
        <span class="o">}</span>
        <span class="c1">// 打印最后结果，注意与创建时表示长度的 dp[n+1][capacity] 区分开，不要写错</span>
        <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">capacity</span><span class="o">]);</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>输入：</p>
<p>```:no-line-numbers
10 4
2 1
3 3
4 5
7 9
<div class="highlight"><pre>输出：

```:no-line-numbers
0 0 1 1 2 2 3 3 4 4 5 
0 0 1 3 3 4 6 6 7 9 9 
0 0 1 3 5 5 6 8 10 10 11 
0 0 1 3 5 5 6 9 10 10 12 
12
</pre></div></p>
<p>可以看出这个输出与前面思路一的输出有区别。</p>
<p>但是如果我们将上边 <code>j</code> 的循环变为倒着算：</p>
<h5 id="_13">参考代码二（正确）<a class="headerlink" href="#_13" title="Permanent link"></a></h5>
<div class="highlight"><pre><span class="kn">package</span> <span class="nn">sing</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.*</span><span class="o">;</span>

<span class="cm">/**</span>
<span class="cm"> * @author xing</span>
<span class="cm"> * @date 2022/2/27 14:09</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Main</span> <span class="o">{</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Scanner</span> <span class="n">sc</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Scanner</span><span class="o">(</span><span class="n">System</span><span class="o">.</span><span class="na">in</span><span class="o">);</span>
        <span class="kt">int</span> <span class="n">capacity</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="c1">// 创建 dp 数组, dp[容量+1]</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">dp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="c1">// 初始化数组</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
        <span class="o">}</span>

        <span class="c1">// 创建 w[], c[]</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">w</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">c</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="c1">// 索引为0处设置为0，后边索引都是1开始，所以没必要</span>
        <span class="c1">// w[0]=0;</span>
        <span class="c1">// c[0]=0;</span>

        <span class="c1">// 遍历获取物品信息，从 1 开始，赋值给数组</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="c1">// 所占容量</span>
            <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
            <span class="c1">// 价值</span>
            <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="o">}</span>

        <span class="c1">// 遍历物品数量</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="c1">// 遍历背包容量</span>
            <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
                <span class="c1">// 背包容量大于等于所占容量</span>
                <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]){</span>
                    <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
                <span class="o">}</span>
            <span class="o">}</span>
            <span class="c1">// 输出dp表</span>
            <span class="k">for</span> <span class="o">(</span><span class="n">Integer</span> <span class="n">integer</span> <span class="o">:</span> <span class="n">dp</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">print</span><span class="o">(</span><span class="n">integer</span> <span class="o">+</span> <span class="s">&quot; &quot;</span><span class="o">);</span>
            <span class="o">}</span>
            <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">();</span>
        <span class="o">}</span>
        <span class="c1">// 打印最后结果，注意与创建时表示长度的 dp[n+1][capacity] 区分开，不要写错</span>
        <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">capacity</span><span class="o">]);</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>就会得到输出：</p>
<p>```:no-line-numbers
0 0 1 1 1 1 1 1 1 1 1 
0 0 1 3 3 4 4 4 4 4 4 
0 0 1 3 5 5 6 8 8 9 9 
0 0 1 3 5 5 6 9 9 10 12 
12
<div class="highlight"><pre>就与思路一得到的结果非常类似。

##### 两个代码比较

其实参考代码一是有问题的。

两种分析方法：

- 第一种分析方法

  对于判断 `j &gt;= w[i]` 显然，按正序来，当前面符合条件的时候，后边一定符合，

  即都会运行里边的代码，

  此时都是能拿的情况

  对于 `dp[j] = Math.max(dp[j], dp[j-w[i]]+c[i])` 其中 `dp[j-w[i]]` 就用到了前面的值。

  且每个 `i` 的循环内，`i` 的值显然是不变的，

  那么代码 `dp[j] = Math.max(dp[j], dp[j-w[i]]+c[i])` 中，

  假如有存在拿起时最大价值大于不拿起最大价值 `dp[j-w[i]]+c[i] &gt; dp[j]`，

  然后后边也是 `dp[j-w[i]]+c[i] &gt; dp[j]`，并且 `dp[j-w[i]]` 就是前面这一个已经拿过物品 `i` 的，那么这里又要拿一次，显然与问题条件不符。

- **第二种分析方法**（推荐）

  通过思路一参考代码的代码以及其 `dp` 表，人家 `dp[i-1][j-w[i]]`，

  使用的是切切实实的只能拿 `i-1` 个物品时的最大价值，或者说对 `i-1` 个物品判断能不能拿，拿不拿，后的最大价值。

  而这里如果先计算前面，那么 `dp[j-w[i]]` 这个位于数组中 `dp[j]` 前面的值，就会被更新，

  当运行代码去更新 `dp[j]` 的时候要用到的 `dp[j-w[i]]`，

  就是已经经过计算的，这个循环内的新值，相当于二维数组的 `dp[i][j-w[i]]`

  而不是需要的旧值，相当于二维数组的 `dp[i-1][j-w[i]]`。

&gt; 例子：
&gt; 
&gt; - 假设第一种物品 所占容量为1，价值为 5，已知数组内元素均初始化为0，i 和 j 都是从1开始
&gt; 
&gt;   那么 `dp[1]=Math.max(0, 5+dp[1-1])=5`，然后得到 `dp[2]=Math(0, 5+dp[2-1])=10`
&gt; 
&gt;   可以看到，背包容量2时，这里的最大价值计算用到了两次第一种物品，与条件最多拿一次相悖。
&gt; 
&gt; - 回过去看 [01背包问题_思路二_参考代码一][01背包问题_思路二_参考代码一] 下的输出，会发现就出现了这种情况。只是最后答案恰巧一样罢了。

为了防止这种情况，我们采用倒序的方式。

引出两个问题：

- 为什么倒序可以防止这种情况？

  根据前面说的两种分析方法所说，这里也分两种回答：

  - 前面符合条件的，后边不一定符合。

    并且代码 `dp[j]=Math.max(dp[j], dp[j-w[i]])`

    中的 `dp[j-w[i]]` 在 `dp[j]` 的前面，有两种情况

    - 是第一次循环，那么这个值肯定是初始化的 0，不会有拿起了物品的情况

    - 不是第一次循环，那就是上一次，那么上一次循环，代表对上一个物品的判断，拿不拿的起，以及拿不拿，不可能拿到这个循环里判断的这个物品。

    所以倒序可以防止这种情况。

  - （推荐）**先算后边的，就不会替换掉前面需要用到的旧值。所以可以得到正确结果。**

- 为什么前面思路一的参考代码里正序没有问题？

  通过查看代码，结合输出的 `dp` 表可以发现，

  因为思路一里用的是切切实实的 `dp[i-1][j-w[i]` 是 `i-1` 那一行的最大价值，就是对上一个物品判断后得到的最大价值。

  而不是思路二里参考代码一那样，正序计算的话，后边使用的前面的值已经不是旧的值了。而是自己已经计算过的新的值。

::: tip 使用正序

如果要正序，可以在 `j` 循环的前面，使用一个数组 `g[]` 来备份 `dp[]` 数组，就不怕数据的更新了。不过会消耗更多的空间。

```java
int[] g = Arrays.copyof(dp, dp.length);
</pre></div></p>
<p>注意，<code>Java</code> 中不要直接用下边的代码：</p>
<div class="highlight"><pre><span class="kt">int</span><span class="o">[]</span> <span class="n">g</span> <span class="o">=</span> <span class="n">dp</span><span class="o">;</span>
</pre></div>

<p>因为两个会指向一个地方，也就是 dp 数组变化，g 数组也会变化，更像是取了个别名，失去了备份的意义。</p>
<p>:::</p>
<hr />
<p>思考： 思路一循环里用到了 i 和 j，所以其中内外层的循环是否可以互换。</p>
<p>如果可以，互换后，可不可以转换为思路二的形式，怎么转换？</p>
<blockquote>
<p>tips: 不想思考，反正我不想</p>
</blockquote>
<hr />
<h5 id="_14">代码细节优化<a class="headerlink" href="#_14" title="Permanent link"></a></h5>
<p>对于 </p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]){</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>其中 <code>j</code> 循环中条件是 <code>j &gt;= 1</code>，下边判断是 <code>j &gt;= w[i]</code>，因为 <code>w[i]</code> 肯定大于0，</p>
<p><code>j</code> 是整数，对 <code>j</code> 来说，<code>j &gt;= 0.1</code> 与 <code>j &gt;= 1</code> 两个判断的结果都是一样的。</p>
<p>所以我们也不用在意 <code>w[i]</code> 是 <code>int</code> 还是 <code>double</code> 类型</p>
<p>完全可以通过将循环的判断条件，改为 <code>j &gt;= w[i]</code>，简化代码</p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
        <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p><strong>缺点</strong></p>
<p>如果说缺点的话，相比较开始的 <code>if</code> 判断，代码会更不宜理解。</p>
<h3 id="dp">一维dp数组初始化的细节问题<a class="headerlink" href="#dp" title="Permanent link"></a></h3>
<h4 id="_15">要求背包必须被装满<a class="headerlink" href="#_15" title="Permanent link"></a></h4>
<p>初始化代码：</p>
<blockquote>
<p>dp[0]初始化为0，（背包容量为0，最大价值一定为0）</p>
<p>其他初始化为 负无穷</p>
</blockquote>
<div class="highlight"><pre><span class="kt">int</span> <span class="n">dp</span><span class="o">[]</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>

<span class="n">dp</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
  <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">Integer</span><span class="o">.</span><span class="na">MIN_VALUE</span><span class="o">;</span>
<span class="o">}</span>
</pre></div>

<p>先看 <code>for</code> 循环的代码：</p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]){</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>显然，一开始，就是倒着循环的，这样，<code>dp[j] = Math.max(dp[j], c[i]+dp[j-w[i]]);</code> </p>
<p>由于 <code>c[i] + dp[j-w[i]]</code> 差不多还是 <code>Integer.MIN_VALUE</code>，所以就是，<code>dp[j] = dp[j]</code>，还是 <code>Integer.MIN_VALUE</code>，没有任何变化，</p>
<p>因为剩下的背包还没有装任何东西，或者或，装不满。</p>
<p>只有当物品所占容量与背包容量相等时，<code>dp[j-w[i]]</code> 取到 0，此时，<code>dp[j] = c[i] + dp[j-w[i]]</code></p>
<p>也就是第一次循环做的事就是，将背包容量与物品所占容量恰好相等即，能装满的位置赋值为此时物品的价值。</p>
<p>再看第二层循环，会赋两个值，</p>
<p>一个是 <code>dp[j-w[i]]</code> 索引位置与上一个赋值的位置一样，代表拿这两个物品，此时背包恰好装满，此时 <code>dp[j]</code> 更新前应该是 <code>Integer.MIN_VALUE</code>，所以更新后就是 <code>c[i] + dp[j-w[i]]</code>，两个物品的价值。</p>
<p>一个是 背包容量与第二个物品所占容量恰好相等的位置，赋值当前物品价值。</p>
<p>依次类推，只有有能装满的情况，才会有赋值，其他的都是 <code>Integet.MIN_VALUE</code>，最后获得的就是装满获得的最大价值。</p>
<p>如果最后输出为 <code>Integer.MIN_VALUE</code> 或者说是 $-2^{31}=-2147483648$，那就是装不满。</p>
<blockquote>
<p>假如容量 20 的背包 5件物品</p>
<p>输入：</p>
<p><code>:no-line-numbers
20 5
2 1
3 10000
4 2
6 3
8 4</code></p>
<p>那最后获得的结果应该是 1 + 2 + 3 + 4 = 10</p>
</blockquote>
<h4 id="_16">不要求背包必须装满<a class="headerlink" href="#_16" title="Permanent link"></a></h4>
<p>初始化代码：</p>
<blockquote>
<p>全部初始化为0</p>
</blockquote>
<div class="highlight"><pre><span class="kt">int</span><span class="o">[]</span> <span class="n">dp</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>

<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
  <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="o">}</span>
</pre></div>

<p>还是看 <code>for</code> 循环代码：</p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]){</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>数组全赋值为0，</p>
<p>第一次循环，不管能不能装满，<code>dp[j] = Math.max(dp[j], c[i] + dp[j-w[i]]);</code></p>
<p>从后往前循环，那么第一次循环里要判断的 <code>dp[j]</code> 与 <code>dp[j-w[i]]</code> 都是 0，</p>
<p>所以，第一次循环内，只要能装下物品的，不管能不能装满，都会被赋值 <code>dp[j]=c[i]</code>，</p>
<p>第二次循环也是，能装下就装，比较没装的，取最大值</p>
<p>依次类推，</p>
<p>最后得到的结果，就是不要求装满的能获得的最大值。</p>
<blockquote>
<p>还是上边的例子</p>
<p>假如容量 20 的背包 5件物品</p>
<p>输入：</p>
<p><code>:no-line-numbers
20 5
2 1
3 10000
4 2
6 3
8 4</code></p>
<p>那最后获得的结果应该是 1 + 10000 + 3 + 4 = 10008</p>
</blockquote>
<h3 id="dp_1">二维dp数组初始化的细节问题<a class="headerlink" href="#dp_1" title="Permanent link"></a></h3>
<p>参照前面对一维dp数组优化。</p>
<p>一想就知道了，下边就不分析了，直接贴代码。</p>
<h4 id="_17">要求背包必须被装满<a class="headerlink" href="#_17" title="Permanent link"></a></h4>
<p>代码：</p>
<div class="highlight"><pre><span class="n">Integer</span><span class="o">[][]</span> <span class="n">dp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">][</span><span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>

<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">dp</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="n">j</span><span class="o">]=</span><span class="n">Integer</span><span class="o">.</span><span class="na">MIN_VALUE</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="mi">0</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
<span class="o">}</span>
</pre></div>

<h4 id="_18">不要去背包必须装满<a class="headerlink" href="#_18" title="Permanent link"></a></h4>
<p>代码：</p>
<div class="highlight"><pre><span class="n">Integer</span><span class="o">[][]</span> <span class="n">dp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">][</span><span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>

<span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">dp</span><span class="o">[</span><span class="mi">0</span><span class="o">][</span><span class="n">j</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">][</span><span class="mi">0</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
<span class="o">}</span>
</pre></div>

<h3 id="01_1">01背包中的一个常数优化<a class="headerlink" href="#01_1" title="Permanent link"></a></h3>
<p>还是先看前面的两个 <code>for</code> 循环:</p>
<p>(通过前面的 <a href="#代码细节优化">01背包问题_思路二_代码细节优化</a>优化后的代码)</p>
<div class="highlight"><pre><span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
  <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
    <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
  <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>倒序，每次循环会用到 <code>dp[i-1][j]</code> 和 <code>dp[i][j-w[i]]</code>，</p>
<p>其中 <code>j-w[i]</code> 为拿起第 <code>i</code> 件物品后的背包剩余容量，</p>
<p>然后我们其实只需要最后的值，我们从最后往前推，都要考虑拿不拿</p>
<!-- 假如后边每个物品都拿了，但是剩余的背包容量还是大于当前物品所占容量， -->

<p>假如极端情况下，后边每个物品都被拿了，背包容量要减去他们的和，</p>
<p>从后往前，到（当前的） <code>i</code> 需要比较的两个值是，</p>
<p><code>dp[i-1][capacity-w[i+1]-w[i+2]-w[...]-w[n]]</code>, </p>
<p><code>dp[i][capacity-w[i]-w[i+1]-w[...]-w[n]]</code></p>
<blockquote>
<p>其中，<code>capacity-w[i+1]-w[i+2]-w[...]-w[n]</code>，为从后往前推拿去后边所有物品后的值，</p>
<p>为我们需要用到的 <code>j</code> 循环中的某个 <code>j</code> 值，或者说某个背包容量，或者说剩下的背包容量。</p>
<p>为什么是某个，因为当前是极端情况下，在已知会拿谁的情况下，从后往前推，值是确定的</p>
</blockquote>
<p>其中，由于是倒序，所以我们从 <code>dp[i-1][j]</code>, <code>dp[i][j-w[i]]</code> 就可以知道只要</p>
<p>想缩小范围，只需要看后者，也就是 <code>dp[i][capacity-w[i]-w[i+1]-w[...]-w[n]]</code></p>
<p>已知需要的是背包容量为 <code>capacity-w[i]-w[i+1]-w[...]-w[n]</code> 时的值，</p>
<p>那么它之前的其实都用不到了，或者说循环不必再运行下去了</p>
<p>并且前面我们说的是极端情况，假如后边更少的物品被选择，<del>那么剩下的容量或者说最后的结果只会更大，</del></p>
<p>就会要用容量更大的，数组的值，也就是要的将是数组后边的值，所以在这个之前的我们还是都用不到，</p>
<p>并且我们说的是容量，不是值，是确定的。</p>
<p>所以我们就可以通过这个确定范围，以 <code>capacity-sum{w[i...n]}</code> 为界限，我们只需要背包容量</p>
<p><code>j &gt;= capacity-sum{w[i...n]}</code>，</p>
<p>这样，背包容量小于这个前面得到的结果的，就都不会再去算了</p>
<p>加上前面的 <code>j &gt;= w[i]</code></p>
<p>最后的范围逻辑代码应该是 <code>j &gt;= max(capacity-sum{w[i...n]}, w[i])</code></p>
<details>

<summary>之前的错误推断</summary>

> ~~下边这是废话~~
> 
> ~~也很好理解，前面说了，只会用到前面极端情况下容量或更大容量，当 `capacity-sum` 更大，~~
> 
> ~~就不可能用到前面的容量更小的值了，所以是 `j >= capacity - sum`~~
> 
> ~~如果 `capacity-sum` 小于 `w[i]`，那么就有可能用到的是大于等于 `capacity-sum` 的值，那么就用更大的 `w[i]`，~~
> 
> ~~别忘了，这个 `w[i]` 确定范围的来源是 `if` 语句转换来的。确定的范围。~~

~~`dp[i+1][capacity-w[i+1]-w[..]-w[n]]`，~~

~~此时的容量，还是大于当前循环的 `j`，那么当前循环，肯定是前面都用不上了。~~


~~里边 `for` 循环范围是 `capacity to 1`w[i]，~~

~~是倒着的，我们只需要最后的 `dp[j]` 的值，也就是 `dp[n]`~~

~~通过代码看，我们只需要知道 `dp[j-w[i]]` 即可。~~

~~那么在内循环中，可以看做 `j` 循环一圈，但我们需要的只有那一个，~~

~~，也就是上一个循环中索引为 `j-w[i]` 的，当时的索引为 `j` 的值，~~

~~那么也就是说，再往后的循环就是多余的，我们考虑的就是再次缩小范围~~

~~能不能在其他地方找~~


~~代码中，还有 `dp[j]`，但从二维数组看，循环倒序每次第一个就是更新它，~~

~~所以不影响我们对范围的考虑~~

~~我们只需要对 `dp[j-w[i]]` 的问题考虑就好了~~

~~以此类推，对 `j` 容量的背包，~~

~~我们主需要知道 `dp[j-w[]]`~~

---

~~对于 `dp[i][j]`，倒着算，我们实际上只需要，`dp[i-1][j]` 和 `dp[i-1][j-w[i]]`~~

~~一维数组就是对于 `dp[j]`，我们倒着算，只需要 `dp[j]` 和 `dp[j-w[i]]` 就行了~~

~~因为是倒着算，所以前面的 `dp[i-1][0] ~ dp[i-1][j-w[i]-1]` 或者说 `dp[0] ~ dp[j-w[i]-1]` 是没有用的，~~

~~也就是 `j < dp[j-w[i]]` 的值是没用的。~~

~~而我们每次计算的是当前数组，不能再去时光倒流告诉上一个，算到这就行了~~

~~// TODO~~

</details>

<p>容易看出，当背包容量 <code>capacity</code> 比较大的时候，会比较好用</p>
<p>越大，就越容易出现 <code>capacity-sum{w[i..n]} &gt; w[i]</code>，</p>
<p>相比于之前的 <code>j &gt;= w[i]</code>，循环次数就会更少，</p>
<blockquote>
<p>注意 <code>capacity-sum{w[i..n]}</code> 与 <code>w[i]</code> 的区别：</p>
<ul>
<li><code>j &gt;= capacity-sum{w[i..n]}</code> 是对于我们最后要的值，所有满足 <code>j &lt; capacity-sum</code> 的我们都不需要，所以不去计算了。</li>
</ul>
<p>当 <code>capacity-sum{w[i..n]} &gt; w[i]</code>，那么二者中间的值因为不做计算，就不能再确保是最大价值。</p>
<ul>
<li><code>j &gt;= w[i]</code> 是 <code>j &lt; w[i]</code> 的时候，我们拿不动物品 <code>i</code>，最大价值继承了之前的值。而不是不去计算。</li>
</ul>
</blockquote>
<h2 id="_19">二、完全背包问题<a class="headerlink" href="#_19" title="Permanent link"></a></h2>
<h3 id="_20">题目描述<a class="headerlink" href="#_20" title="Permanent link"></a></h3>
<p>设有 n 中物品，没中物品有一个重量及一个价值，但没中物品的数量是无限的，同时有一个背包，最大载重量为M, 今从 n 中物品中选取若干件（同一种物品可以多次选取），是其重量的和小于等于M，而价值的和最大。</p>
<p>输入：</p>
<p>第一行，两个整数 M (M ≤ 2000)，和物品数量 N (N ≤ 30)</p>
<p>第2&hellip;N+1行，每行两个整数 Wi, Ci 表示每个物品的重量和价值。</p>
<h3 id="_21">特点<a class="headerlink" href="#_21" title="Permanent link"></a></h3>
<p>同一种物品可以被任意次的选取</p>
<p>或者说</p>
<p>每种物品的数量都达到或者超过了背包能容纳该物品数量的上限。</p>
<h3 id="_22">思路<a class="headerlink" href="#_22" title="Permanent link"></a></h3>
<h4 id="_23">思路一<a class="headerlink" href="#_23" title="Permanent link"></a></h4>
<h5 id="_24">分析<a class="headerlink" href="#_24" title="Permanent link"></a></h5>
<p>物品无限，但是背包容量有限，能容纳的物品数量其实有限</p>
<p>转换为01背包，通过01背包的代码思考：</p>
<div class="highlight"><pre><span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
  <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
    <span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
      <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
    <span class="o">}</span>
  <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>还是要用到之前的值。</p>
<p>那么因为可以拿任意个，准确的说是可以拿 <code>0 ~ j/w[i]</code> 个，也就是最少不拿，最多拿到拿不下。</p>
<p>那么之前是判断，能不能拿，拿不拿。现在就是判断，能不能拿，以及拿几个。</p>
<p>拿一个的值，拿两个的，，，就要再用到循环，</p>
<p>别忘了在循环内比较上一个循环得到的能获得的最大价值与当前循环计算结果的大小。</p>
<p>就是要再加一层循环 <code>for(int k = 0; k &lt;= j/w[i]; k++)</code></p>
<p>这里 <code>k</code> 为 <code>0</code> 时就是代表不拿，不拿就是 <code>dp[i-1][j]</code> 一维数组里也就是 <code>dp[j]</code>（前面<a href="#思路二-优化">01背包问题_思路二</a>已经说了），没有意义。所以这里的 <code>k</code> 应该直接从 <code>1</code> 开始。</p>
<p>并且 <code>k</code> 从 <code>1</code> 开始，判断条件 <code>k &lt;= j/w[i]</code> 也就是满足条件就要 <code>j &gt;= w[i]</code> 下边的代码才会执行，所以，原代码里的 <code>if</code> 判断就可以不要了。</p>
<h5 id="_25">参考代码<a class="headerlink" href="#_25" title="Permanent link"></a></h5>
<p>保留 <code>if</code> 判断参考代码：</p>
<div class="highlight"><pre><span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
  <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
    <span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
      <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">j</span><span class="o">/</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">k</span><span class="o">++)</span> <span class="o">{</span>
        <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span><span class="o">]);</span>
      <span class="o">}</span>
    <span class="o">}</span>
  <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>删除 <code>if</code> 判断参考代码：</p>
<div class="highlight"><pre><span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
  <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">j</span><span class="o">/</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">k</span><span class="o">++)</span> <span class="o">{</span>
      <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span><span class="o">]);</span>
    <span class="o">}</span>
  <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<hr />
<p>输入：</p>
<p>```:no-line-numbers
10 4
2 1
3 3
4 5
7 9
<div class="highlight"><pre>输出：

```:no-line-numbers
0 0 1 1 2 2 3 3 4 4 5 
0 0 1 3 3 4 6 6 7 9 9 
0 0 1 3 5 5 6 8 10 10 11 
0 0 1 3 5 5 6 9 10 10 12 
12
</pre></div></p>
<p>对于这个输出，明显可以发现，他与<a href="#参考代码一-错误">01背包问题_思路二_参考代码一</a> 这个错误的01背包问题的代码输出的内容一样。</p>
<p>又一次验证了这个代码确实重复选择了选择过的物品。</p>
<p>那能不能说明这个代码其实是完全背包的另一个一维数组代码？</p>
<p><del>不能，并且不是。因为这个代码每个循环里只是判断的能不能拿，以及拿不拿（一个）的事情。而不是考虑拿几个才能得到能获得的最大价值。</del></p>
<p><del>所以这个结果的重复与这个代码的最大价值结果和正确代码的结果一样类似，是偶然性的。</del></p>
<p>上边说错了，确实可以！<a href="#分析-3">完全背包问题_思路二_分析</a> 里说明，确实这个代码就是完全背包的一维数组代码。也是下边的<a href="#思路二-优化-1">思路二</a> 的代码。</p>
<p>上边错了那就要按前面想法，分析为什么可以？</p>
<p>因为正序算，要用到前面的 <code>dp[j-w[i]]</code> 作比较这里它可以拿，再往前它的 <code>dp[j-w[i]]</code> 也可以拿，也就是可以选择一直拿，那就相当于可以随便拿，就是完全背包问题。</p>
<h4 id="_26">思路二（优化）<a class="headerlink" href="#_26" title="Permanent link"></a></h4>
<h5 id="_27">优化内容<a class="headerlink" href="#_27" title="Permanent link"></a></h5>
<ul>
<li>优化<code>for</code> 循环嵌套过多的问题</li>
</ul>
<p>不难看出，上边的<a href="#思路一-1">完全背包问题_思路一</a>中，<code>for</code> 嵌套的循环过于多了。这里优化的就是这个。</p>
<h5 id="_28">分析<a class="headerlink" href="#_28" title="Permanent link"></a></h5>
<p>我们这里回到二维数组，用 <code>dp[i][j]</code></p>
<p>重新通过开始的思路一到思路二的方向去做，</p>
<p>二维数组正序的去算，我们还是一个的拿，拿之后剩下背包要拿啥，还是利用前面的信息，</p>
<p>不同的是，之前01背包我们只能拿一个，所以相当于拿了之后只能拿前 <code>i-1</code> 件物品，所以剩下背包容量能获得的最大价值是 <code>dp[i-1][j-w[i]]</code>，</p>
<p>现在还能拿前 <code>i</code> 件物品，所以是 <code>dp[i][j-w[i]]</code></p>
<p>发现</p>
<ul>
<li>拿不了</li>
</ul>
<p><code>dp[i][j]=dp[i-1][j]</code></p>
<ul>
<li>能拿</li>
</ul>
<p><code>dp[i][j]=Math.max(dp[i-1][j], dp[i][j-w[i]]+c[i])</code></p>
<p>至于拿不拿第二个，那就是前面 <code>dp[i][j-w[i]]</code> 要去考虑的问题。</p>
<blockquote>
<p>可以发现，这里的关键就是，让要用到的前面的数据，也去考虑拿第 <code>i</code> 物品。而不是 <code>i-1</code> 件物品。</p>
</blockquote>
<p>转化到一维呢？</p>
<p>与之前01背包的一维数组<a href="#两个代码比较">01背包问题_思路二_两个代码比较</a>结合，</p>
<p>我们就是要正序运行，这样，对 <code>dp[j]</code> 更新的时候，用到的 <code>dp[j-w[i]]</code> 就是这个循环内已经更新过的新值，相当于 <code>dp[i][j-w[i]]</code></p>
<blockquote>
<p>隐含使用信息：</p>
<p>循环到 <code>dp[i][j]</code> 使用了代码 <code>dp[i][j]=...</code> 才会去修改它，其他索引下数据只会获取，不会修改</p>
</blockquote>
<p>所以，我们这里的代码就是，使用前面的<a href="#参考代码一-错误">01背包问题_思路二_参考代码一</a>这个当时错误的方式。正序算。</p>
<p>即</p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="c1">// 遍历背包容量</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
        <span class="c1">// 背包容量大于等于所占容量</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]){</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<h5 id="_29">参考代码<a class="headerlink" href="#_29" title="Permanent link"></a></h5>
<p>把原来关于 <code>j</code> 循环的倒序改为正序就好了。</p>
<p>就是 <a href="#参考代码一-错误">01背包问题_思路二_参考代码一</a> 这个01背包问题中错误的代码。</p>
<div class="highlight"><pre><span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
  <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
      <span class="c1">// </span>
      <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
    <span class="o">}</span>
  <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<h5 id="_30">代码细节优化<a class="headerlink" href="#_30" title="Permanent link"></a></h5>
<blockquote>
<p>隐含条件：物品重量大于0</p>
<p>物品重量等于0，价值等于0，没意义。</p>
<p>物品重量等于0，价值大于0，能获得的最大价值就无限了，也没意义</p>
<p>所以 <code>w[i] &gt; 0</code> </p>
</blockquote>
<p><strong>内容</strong></p>
<p>与前面的 <a href="#代码细节优化">01背包问题_思路二_代码细节优化</a> 不同，优化前的代码中 <code>j</code> 的循环虽然只是由倒序变为了正序，</p>
<p>但这个就有不适用的情况。前面那个只是用来比较大小，这个确是要赋给 <code>int</code> 类型的变量作初始值。</p>
<p>看这个代码，中间 <code>j</code> 循环从 <code>1</code> 开始</p>
<p>下边又要判断 <code>j &gt;= w[i]</code>，</p>
<p>所以，对于 <code>int</code> 类型的 <code>w[i]</code>，我们可以直接在循环内初始条件从 <code>j=w[i]</code> 开始，省去无意义循环。（默认 <code>w[i] &gt; 0</code>）</p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
      <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>但是要注意，这么做就要求必须这个 <code>w[i]</code> 数组内都为 <code>int</code> 类型，</p>
<p>如果 <code>w[i]</code> 是 <code>double</code> 类型，要将 <code>j &gt;= w[i]</code> 放入循环初始化中，初始化为满足条件的值，</p>
<p>就需要通过 <code>Math.ceil()</code> 方法，将 <code>w[i]</code> 向上取整，并在前面加上 <code>(int)</code> 类型转换</p>
<p>并且 <code>Math.ceil()</code> 的参数只能是 <code>double</code> 类型。所以不同类型的 <code>w[i]</code>，代码不能合并。</p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="o">(</span><span class="kt">int</span><span class="o">)</span><span class="n">Math</span><span class="o">.</span><span class="na">ceil</span><span class="o">(</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
      <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]+</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]]);</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p><strong>缺点</strong></p>
<p>同样的缺点大概就是不宜理解。</p>
<h3 id="_31">其他优化<a class="headerlink" href="#_31" title="Permanent link"></a></h3>
<blockquote>
<p>其实对这个问题很容易想到，优先拿性价比最高的物品，最后平均下来的性价比越高，相同重量下总价值就越大。</p>
</blockquote>
<ul>
<li>
<p>去掉任何情况下可以被其他物品上位代替的物品</p>
</li>
<li>
<p>假如有两个物品 i, j，满足所占容量 <code>w[i] &lt; w[j]</code>，且价值 <code>c[i] = c[j]</code>，</p>
<p>那么就可以将物品 <code>j</code> 去掉，不去考虑。</p>
</li>
<li>
<p>假如有两个物品 i, j, 其中 <code>w[i] &lt; w[j]</code>，</p>
<p>若满足 <code>w[j] % w[i]=0</code>, </p>
<p>且 <code>c[i]/w[i] &gt; c[j]/w[j]</code>，或者 <code>c[i] * (w[j] / w[i]) &gt; c[j]</code> 或 <code>c[i] * w[j] &gt; c[j] * w[i]</code></p>
<p>即 物品 j 的重量 是 物品 i 重量的倍数，且 i 的性价比更高。</p>
<p>那么就可以将 物品 <code>j</code> 去掉，不去考虑。</p>
</li>
</ul>
<blockquote>
<p>对于 随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度 </p>
<p>(<a href="https://www.cnblogs.com/coded-ream/p/7208019.html">背包问题（背包九讲）</a>)</p>
</blockquote>
<p>此方法不能改善最坏情况，可能一件物品也去不掉。</p>
<h2 id="_32">三、多重背包问题<a class="headerlink" href="#_32" title="Permanent link"></a></h2>
<h3 id="_33">问题描述<a class="headerlink" href="#_33" title="Permanent link"></a></h3>
<p>容量为 <code>capacity</code> 的背包，有 <code>n</code> 中物品，第 <code>i</code> 中物品最多有 <code>n[i]</code> 件可用。</p>
<p>求能放入背包的最大价值。</p>
<p><strong>输入</strong></p>
<p>第一行 容量 M，物品数 N</p>
<p>第2..N+1 行，每行三个数，所占容量，价值，与物品数量</p>
<h3 id="_34">特点<a class="headerlink" href="#_34" title="Permanent link"></a></h3>
<p>物品只有有限个，</p>
<blockquote>
<p>既不是01背包中每件物品只有一个，也不是像完全背包中物品可以无限选取</p>
</blockquote>
<p>隐含条件：至少存在一个物品的数量大于0且少于背包能容纳的该物品数量的上限</p>
<h3 id="_35">思路<a class="headerlink" href="#_35" title="Permanent link"></a></h3>
<h4 id="_36">胡乱分析<a class="headerlink" href="#_36" title="Permanent link"></a></h4>
<ul>
<li>一</li>
</ul>
<p>很容易根据前面想到，前面用到了加一层循环 <code>k</code>，来判断拿不同数量的物品，能获得的最大价值是哪个，之前是 <code>k &lt;= j/w[i]</code>，</p>
<p>这里把 <code>j/w[i]</code> 换成每件物品的数量 <code>n[i]</code> 不就行了么，同时注意 <code>n[i]</code> 不能大于 <code>j/w[i]</code>，所以应该换成 <code>Math.min(j/w[i], n[i])</code></p>
<p>问题就还是三层 <code>for</code> 嵌套，不好</p>
<ul>
<li>二</li>
</ul>
<p>根据有限性，将物品拆分开，假装看为不同的物品，转换为01背包问题。</p>
<p>缺点就是如果物品数量很大，</p>
<p>拆分开就代表还是要对物品数量做一个 <code>for</code> 循环</p>
<p>每件物品都去判断，非常浪费时间，</p>
<p>与前面的一是一模一样的。</p>
<p>开始加 <code>k</code> 的 <code>for</code> 循环就是增加计算拿几个的价值多少，每个都去算一次，这与上边不一样了么。</p>
<h4 id="_37">思路一<a class="headerlink" href="#_37" title="Permanent link"></a></h4>
<h5 id="_38">分析<a class="headerlink" href="#_38" title="Permanent link"></a></h5>
<p>根据物品的有限性，我们可以将物品拆分开，假装看做不同的物品</p>
<p>然后通过01背包的方法去解决。</p>
<p>那么就可以简单的在原有三层 <code>for</code> 循环的 <a href="#参考代码-1">完全背包问题_思路一_参考代码</a>上，</p>
<p>一是增加新输入信息的获取，</p>
<p>二是将 <code>k</code> 循环，变为物品数量的 <code>for</code> 循环</p>
<h5 id="_39">参考代码<a class="headerlink" href="#_39" title="Permanent link"></a></h5>
<div class="highlight"><pre><span class="kn">package</span> <span class="nn">sing</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.*</span><span class="o">;</span>

<span class="cm">/**</span>
<span class="cm"> * @author xing</span>
<span class="cm"> * @date 2022/2/27 14:09</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Main</span> <span class="o">{</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Scanner</span> <span class="n">sc</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Scanner</span><span class="o">(</span><span class="n">System</span><span class="o">.</span><span class="na">in</span><span class="o">);</span>
        <span class="kt">int</span> <span class="n">capacity</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">dp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">capacity</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">i</span><span class="o">]=</span><span class="mi">0</span><span class="o">;</span>
        <span class="o">}</span>

        <span class="n">Integer</span><span class="o">[]</span> <span class="n">w</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">c</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="c1">// 更改部分： 增加 s[]</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">s</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>

        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
            <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
            <span class="c1">// 新增：物品数量输入的获取</span>
            <span class="n">s</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="o">}</span>

        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
                <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]){</span>
                    <span class="c1">// 更改: k 的判断条件</span>
                    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">Math</span><span class="o">.</span><span class="na">min</span><span class="o">(</span><span class="n">j</span><span class="o">/</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">s</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span> <span class="n">k</span><span class="o">++)</span> <span class="o">{</span>
                        <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span><span class="o">]);</span>
                    <span class="o">}</span>
                <span class="o">}</span>
            <span class="o">}</span>
            <span class="k">for</span> <span class="o">(</span><span class="n">Integer</span> <span class="n">integer</span> <span class="o">:</span> <span class="n">dp</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">print</span><span class="o">(</span><span class="n">integer</span> <span class="o">+</span> <span class="s">&quot; &quot;</span><span class="o">);</span>
            <span class="o">}</span>
            <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">();</span>
        <span class="o">}</span>
        <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">capacity</span><span class="o">]);</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<p>这里的 <code>k</code> 循环判断条件也可以改为 </p>
<div class="highlight"><pre><span class="n">k</span> <span class="o">&lt;=</span> <span class="n">s</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">&amp;&amp;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">j</span><span class="o">/</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span>
</pre></div>

<p>并且因为在两层循环内，这里 <code>k</code> 循环也可以倒序，不会影响结果。</p>
<p>输入：</p>
<p>```:no-line-numbers
100 5
8 20 4
4 50 9
3 50 7
4 30 6
2 20 1
<div class="highlight"><pre>输出：

```:no-line-numbers
0 0 0 0 0 0 0 0 20 20 20 20 20 20 20 20 40 40 40 40 40 40 40 40 60 60 60 60 60 60 60 60 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 
0 0 0 0 50 50 50 50 100 100 100 100 150 150 150 150 200 200 200 200 250 250 250 250 300 300 300 300 350 350 350 350 400 400 400 400 450 450 450 450 450 450 450 450 470 470 470 470 470 470 470 470 490 490 490 490 490 490 490 490 510 510 510 510 510 510 510 510 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 530 
0 0 0 50 50 50 100 100 100 150 150 150 200 200 200 250 250 250 300 300 300 350 350 350 350 400 400 400 400 450 450 450 450 500 500 500 500 550 550 550 550 600 600 600 600 650 650 650 650 700 700 700 700 750 750 750 750 800 800 800 800 800 800 800 800 820 820 820 820 820 820 820 820 840 840 840 840 840 840 840 840 860 860 860 860 860 860 860 860 880 880 880 880 880 880 880 880 880 880 880 880 
0 0 0 50 50 50 100 100 100 150 150 150 200 200 200 250 250 250 300 300 300 350 350 350 350 400 400 400 400 450 450 450 450 500 500 500 500 550 550 550 550 600 600 600 600 650 650 650 650 700 700 700 700 750 750 750 750 800 800 800 800 830 830 830 830 860 860 860 860 890 890 890 890 920 920 920 920 950 950 950 950 980 980 980 980 980 980 980 980 1000 1000 1000 1000 1000 1000 1000 1000 1020 1020 1020 1020 
0 0 20 50 50 70 100 100 120 150 150 170 200 200 220 250 250 270 300 300 320 350 350 370 370 400 400 420 420 450 450 470 470 500 500 520 520 550 550 570 570 600 600 620 620 650 650 670 670 700 700 720 720 750 750 770 770 800 800 820 820 830 830 850 850 860 860 880 880 890 890 910 910 920 920 940 940 950 950 970 970 980 980 1000 1000 1000 1000 1000 1000 1000 1000 1020 1020 1020 1020 1020 1020 1020 1020 1040 1040 
1040
</pre></div></p>
<p>时间复杂度: $O(V * \sum s[i])$</p>
<h4 id="_40">思路二（二进制优化）<a class="headerlink" href="#_40" title="Permanent link"></a></h4>
<blockquote>
<p>二进制状态压缩是状态压缩动态规划，宽度优先搜索状态压缩优化的重要基础。</p>
</blockquote>
<h5 id="_41">优化内容<a class="headerlink" href="#_41" title="Permanent link"></a></h5>
<p>通过二进制优化</p>
<blockquote>
<p>通过二进制优化，将 n 个相同物品，转化为更少数量的 只有 1 个的的不同物品，</p>
<p>（本来转化为01背包就是要看做n个不同物品）。</p>
<p>就转化为了01背包问题</p>
</blockquote>
<h5 id="_42">思路扩展（核心）<a class="headerlink" href="#_42" title="Permanent link"></a></h5>
<p><strong>问题</strong></p>
<p>有 1000 个苹果，10 个箱子怎么个方法，不管我想那多少个苹果，都能成箱成箱的拿？</p>
<p><strong>答</strong></p>
<p>利用二进制，如表：</p>
<table>
<thead>
<tr>
<th>$2^0$</th>
<th>$2^1$</th>
<th>$2^2$</th>
<th>$2^3$</th>
<th>$2^4$</th>
<th>$2^5$</th>
<th>&hellip;</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>2</td>
<td>4</td>
<td>8</td>
<td>16</td>
<td>32</td>
<td>&hellip;</td>
</tr>
</tbody>
</table>
<p>要拿一个苹果，就是 1</p>
<p>两个，就是 2</p>
<p>三个，就是 1+2</p>
<p>等等</p>
<p>1000 就是 $2^9+2^8+2^7+2^6+2^5+2^3$ 也就是拿第四、六、七、八、九、十个箱子。</p>
<p><strong>原理</strong></p>
<p>通过二进制的思想，来完成</p>
<p>因为已知 二进制 是可以表示十进制的，例如 0010 就是 2</p>
<p>四位 每位 对应的就是 $2^3$ $2^2$ $2^1$ $2^0$</p>
<p>将箱子看做一个一个二进制，使得箱子内苹果的数量，与 二进制 换算十进制对应的数相同。</p>
<p>那么，要多少个苹果，按二进制的 01 去拿就好了，</p>
<p>10 就是 1010，拿第二和第四个箱子</p>
<p>如果箱子数量的顺序也对应，不是上边的 $2^0 \sim 2^5$， 是 $2^5 \sim 2^0$，就是拿第一个和第三个箱子</p>
<blockquote>
<p>在一家找到的，在另一家也能找到，就是可以说二者等价</p>
<p>并且可以说，</p>
<p>本来 1000 个苹果，1000个物品</p>
<p>现在我们人为分组，分为了 10 组（新物品）。</p>
<p>但是选择这些组，本质还是苹果。</p>
<p>虽然看着选择的是组，</p>
<p>还是可以看做，我们选择的是任意数量的苹果，</p>
</blockquote>
<p><strong>注意</strong></p>
<p>如果十个箱子按二进制装满，应该是 $2^{10}-1=1023$ 个苹果</p>
<p>但是苹果数量不是 1023 ，而是 1000，也就是说，第十个箱子是装不满的，只有 $1000-(2^9-1)=489$ 个苹果。</p>
<p>前九个箱子总数量是 $2^9-1=511$ 个苹果，当需要的苹果数量大于 511 的时候，就 <strong>一定需要</strong> 拿第十个箱子，不拿第十个箱子是拿不够的，。</p>
<p>那么此时需要计算的应该是，先减去最后装不满的第十个箱子的 489 个苹果，然后重新将新结果转换为二进制，去拿对应的箱子。</p>
<p><strong>优点</strong></p>
<p>对于背包问题，显然不管是前面的 01背包，完全背包 还是 前面多重背包的思路一，都可以说我们每个物体都要去判断一次，拿不拿的问题，</p>
<p>(针对优化前的代码，优化后不算)</p>
<p>针对我们多重背包要转化为的01背包问题</p>
<p>买苹果，背包最多能装且有 n 个苹果（<code>k &lt;= Math.min(s[i], j/w[i])</code>，这里就是 <code>k &lt;= n</code>），我们要买 n 个苹果，就要看做 n 个物品，然后就要（第三层 <code>for</code> 循环） n 次。1000个苹果，就是 1000 次。</p>
<p>而用箱子，就只有十个箱子，就是十个物品，就是（第一层 <code>for</code> 循环） 10 次。</p>
<p>还是买苹果，对我们来说，还是能买到范围内任意数量的苹果，花了相同的钱，得到了相同数量的苹果，一切都是一样的，（忽略箱子，概念上的分组）</p>
<p>但是买的次数变少了，最多也不会超过10次。</p>
<p>之前我们将 1000 个苹果看做 1000 个物品，现在我们将一定数量的<strong>相同物品</strong>，通过二进制优化，将 1000 个苹果看做 10 个物品。</p>
<p>大大减少了循环次数。</p>
<h5 id="_43">分析<a class="headerlink" href="#_43" title="Permanent link"></a></h5>
<p>根据前面的思路扩展中的原理及注意</p>
<p>如何通过二进制优化多重背包问题</p>
<p>发现，转化为二进制之后，二进制就是0和1，我们通过这种方式将多重背包问题，转换为了01背包问题</p>
<p>例如</p>
<p>```:no-line-numbers
7 3
2 3 12
3 5 15
1 2 3
<div class="highlight"><pre>第一件物品，12个，拆分为 1, 2, 4, 5 个，共4中物品，

第二件物品，15个，拆分为 1, 2, 4, 8 个，共4种物品

第三节物品，3个，拆分为 1, 2 个，共2种物品

这样，按照原来的[多重背包问题_思路一_分析][多重背包问题_思路一_分析]，是需要拆分为 12+15+3=30 件物品，但是现在被我们拆分为了 4+4+2=10 件物品

新的物品的重量(所占容量)，价值，都是原来的物品乘以个数

对这 10 中物品进行01背包求解就可以了，

&gt; 以第一件物品拆分开举例，因为可以代表任意数量的第一件物品，注意是任意，所以这4件物品，就可以代替原来的10件物品。
&gt; 
&gt; 你要拿 8 件第一件物品，二进制也就是 1000 ，那么与我拿拆分后的第4件物品，是一样的，都占了那么多重量 和 价值。
&gt; 
&gt; 对任意件都是一样的，反过来也是，拆分后4件物品，0100，代表等价于原来的第一件物品拿了4件，二者可以相互代替。

注意，拆分为物品，是拆分为具体的，有自己不同重量和价值的物品，

因为一是不好表示物品的位数，是 2 的几次方，二是还有不是 2 的次方的数。三是二者可以相互代替，所以完全可以这么做。

##### 参考代码

```java
package sing;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int capacity = sc.nextInt();
        int n = sc.nextInt();
        Integer[] dp = new Integer[capacity + 1];
        for (int i = 0; i &lt; capacity + 1; i++) {
            dp[i] = 0;
        }
        Integer[] w = new Integer[n + 1];
        Integer[] c = new Integer[n + 1];
        Integer[] s = new Integer[n + 1];

        // 新的 w[] 和 c[] 不知道具体长度，这里用 ArrayList 表示
        ArrayList&lt;Integer&gt; newW = new ArrayList&lt;&gt;();
        ArrayList&lt;Integer&gt; newC = new ArrayList&lt;&gt;();

        for (int i = 1; i &lt; n + 1; i++) {
            w[i] = sc.nextInt();
            c[i] = sc.nextInt();
            s[i] = sc.nextInt();

            // 循环, 每次左移一位(乘以2)
            for (Integer j = 1; j &lt; s[i]; j = j &lt;&lt; 1) {
                // 放入新的重量与价值数组
                newW.add(w[i] * j);
                newC.add(c[i] * j);

                // 更新未拆分的物品数量
                s[i] -= j;
            }
            // 最后不为0，也就是 s[i] 剩余未拆分物品数量 不满足 2 的 n 次方
            // 乘以剩余数量
            if (s[i] != 0) {
                newW.add(w[i] * s[i]);
                newC.add(c[i] * s[i]);
            }
        }

        // 获取新数组长度，即物品数量
        int newN = newW.size();

        // 与 01 背包相同，但是前面的 newN 就是真实长度，所以这里不用 + 1
        for (int i = 1; i &lt; newN; i++) {
            for (int j = capacity; j &gt;= 1; j--) {
                if (j &gt;= newW.get(i)) {
                    dp[j] = Math.max(dp[j], newC.get(i) + dp[j - newW.get(i)]);
                }
            }
            for (Integer integer : dp) {
                System.out.print(integer + &quot; &quot;);
            }
            System.out.println();
        }
        System.out.println(dp[capacity]);
    }
}
</pre></div></p>
<p>其中的 <code>Integer</code> 均可可以改为 <code>int</code></p>
<p><strong>输入</strong></p>
<p>```:no-line-numbers
7 3
2 3 12
3 5 15
1 2 3
<div class="highlight"><pre>**输出**

```:no-line-numbers
0 0 0 0 6 6 6 6 
0 0 0 0 6 6 6 6 
0 0 0 0 6 6 6 6 
0 0 0 5 6 6 6 11 
0 0 0 5 6 6 10 11 
0 0 0 5 6 6 10 11 
0 0 0 5 6 6 10 11 
0 2 2 5 7 8 10 12 
0 2 4 6 7 9 11 12 
12
</pre></div></p>
<p>时间复杂度: $O(V * \sum \log s[i])$</p>
<h4 id="_44">思路三（单调队列优化）<a class="headerlink" href="#_44" title="Permanent link"></a></h4>
<h5 id="_45">分析<a class="headerlink" href="#_45" title="Permanent link"></a></h5>
<p>附上前面多重背包朴素算法的思路一代码：</p>
<div class="highlight"><pre><span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">j</span><span class="o">--)</span> <span class="o">{</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">Math</span><span class="o">.</span><span class="na">min</span><span class="o">(</span><span class="n">j</span><span class="o">/</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">s</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span> <span class="n">k</span><span class="o">++)</span> <span class="o">{</span>
            <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]=</span><span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span> <span class="o">+</span> <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">-</span><span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]*</span><span class="n">k</span><span class="o">]);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

<ul>
<li>分组</li>
</ul>
<p>我们可以知道，在整个 <code>k</code> 的 <code>for</code> 循环内，一次次作比较，我们将它们写开，</p>
<p>我们作比较用到的数组中的值为 <code>dp[j], dp[j-w[i]], ..., dp[j-w[i]*Math.min(j/w[i], s[i])]</code></p>
<p>最终我们获得的最大的值，为真正的更新后的 <code>dp[j]</code>。也就是前 <code>i</code> 件物品 <code>j</code> 背包容量能获得的最大价值。</p>
<p>可以看出，所用到的作比较的背包容量每两个之间的差都是当前物品的体积 <code>w[i]</code></p>
<p>我们如果就按容量分组（下边称 <code>w[i]</code> 为 <code>v</code>）：</p>
<div class="highlight"><pre>dp[0]  , dp[v]   , dp[2v]  , ..., dp[kv]
dp[1]  , dp[1+v] , dp[1+2v], ..., dp[1+kv]
...
dp[v-1], dp[2v-1], dp[3v-1], ..., dp[(1+k)v-1]
</pre></div>

<p>总共 <code>v-1</code> 组，因为已知 里边有判断条件 <code>j &gt;= w[i]</code>，也就是背包容量小于 <code>v</code> 的跳过。</p>
<p>可以看出按顺序来，是列方向从上到下，然后下一列从上到下，</p>
<p>所以只对背包容量大于 <code>v</code> 的，我们就一定会分为这 <code>v</code> 组。每组至少一个。</p>
<p>这里我们也可以忽略 <code>dp[0]</code>，进行分组:</p>
<div class="highlight"><pre>dp[1], dp[1+v], dp[1+2v], ..., dp[1+kv]
dp[2], dp[2+v], dp[2+2v], ..., dp[2+kv]
...
dp[v], dp[2v] , dp[3v]  , ..., dp[(k+1)v]
</pre></div>

<p>同样，对于 <code>j&gt;=w[i]</code> 也是一定会分为 <code>v</code> 组，每组至少一个。</p>
<p>二者分组数量相等，无非是范围不一样，前者是 <code>[0, v-1]</code>，后者 <code>[1, v]</code></p>
<ul>
<li>使用单调队列</li>
</ul>
<p>已知每个 <code>j</code> 循环，或者分组后，对分组内每个值都要去访问，比较获得最大值，并且 <code>j</code> 为倒序</p>
<p>那么也就是说，当 <code>j</code> 减少一个 <code>v</code> 后，</p>
<p>例如之前 <code>j=3v</code>，访问的就是 <code>dp[0], dp[v], d[2v], dp[3v]</code>，</p>
<p>现在减少一个 <code>v</code> 变为 <code>j=2v</code>, 访问的就是 <code>dp[0], dp[v], dp[2v]</code></p>
<p>也就是说，之前访问过的，又访问了一遍。</p>
<p><code>j</code> 循环内访问的全部的数组值是一定的，</p>
<p>值数量一个一个变，求最值，就想到了我们的单调队列，总共 <code>v</code> 组单调队列。</p>
<p>分为 <code>v</code> 组，然后对每组，通过单调队列求最大值。</p>
<p>（注：不是只能顺序访问值，并且我们通过分组很容易知道要对比的值的位置）</p>
<p>但是我们的队列要是一个一个进队的，也就是要你访问的数量是变多的，</p>
<p>但是我们知道 <code>j</code> 是倒序，减少一个 <code>v</code> 访问数量就会减 1，是减少的。</p>
<p>但是我们单调队列需要正序获取值。并且获得最大值也是正序的。</p>
<ul>
<li>改为正序</li>
</ul>
<p>那我们修改 <code>dp[j]</code> 也要正序，也就是 <code>j</code> 要正序，</p>
<p>但是我们需要旧值，那我们就要用另一个数组 <code>g</code> 在每次对背包容量循环之前先备份。</p>
<p>每次要用的时候就从备份的 <code>g</code> 数组取值，就行了</p>
<ul>
<li>价值的计算</li>
</ul>
<p>再回到单调队列，对 <code>v</code> 组，再往下对组内循环，设为 <code>k</code> 循环，每次 <code>+ v</code>，直接作为索引</p>
<p>那么对索引 <code>k</code> 作比较时，</p>
<p>队列里再往前的元素(假设索引为t)的价值应该是 <code>dpBackups[t] + (k-t)/v * c[i]</code>;</p>
<ul>
<li>单调队列存储内容的选择</li>
</ul>
<p>知道公式，我们就可以根据 <code>k</code> 来计算结果，<code>k</code> 是索引，而 <code>t</code> 也是队列里值对应数组的索引，</p>
<p>本来我们应该再设置一个，用来存储索引，但是我们既然可以直接通过索引计算，就直接存储索引就好了。</p>
<p>这样，也不必再设置一个队列，用来存储索引了。</p>
<ul>
<li>回到上边价值的计算</li>
</ul>
<p>队首价值计算就是 </p>
<p>```java:no-line-numbers
  dpBacups[queue.getFirst()] + (k- queue.getFirst()) / w[i] * c[i];
  <div class="highlight"><pre>与队尾比较就是：

```java:no-line-numbers
dpBackups[k] &gt; dpBackups[queue.getLast()] + (k - queue.getLast()) / w[i] * c[i];
</pre></div></p>
<p>或者用 <code>&gt;=</code></p>
<p>```java:no-line-numbers
  dpBackups[k] &gt;= dpBackups[queue.getLast()] + (k - queue.getLast()) / w[i] * c[i];
  <div class="highlight"><pre>并且对于队首是否超出窗口的判断，也可以知道:

```java:no-line-numbers
queue.getFirst() &lt; k- s[i] * w[i];
</pre></div></p>
<p>或者将 <code>s[i]</code>，改为 <code>Math.min(k / w[i], s[i])</code></p>
<p>最后不要忘了使用判断的时候要加上 <code>queue.size() != 0</code></p>
<h5 id="_46">代码的逐步改进<a class="headerlink" href="#_46" title="Permanent link"></a></h5>
<p>下边逐步改为单调队列形式：</p>
<ol>
<li>那我们先只看最开始的朴素算法，把 <code>j</code> 循环改成顺序：</li>
</ol>
<details>

<p><summary>参考代码</summary></p>
<div class="highlight"><pre><span class="c1">// dp备份数组声明</span>
<span class="n">Integer</span><span class="o">[]</span> <span class="n">dpBackups</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="c1">// 备份，注意不要通过 dpBackups = dp; 方式赋值，</span>
    <span class="c1">// 二者会指向同一位置，dp 变化， dpBackups 也会变化</span>
    <span class="n">dpBackups</span> <span class="o">=</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">copyOf</span><span class="o">(</span><span class="n">dp</span><span class="o">,</span> <span class="n">dp</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
    <span class="c1">// 改为顺序</span>
    <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
        <span class="k">if</span> <span class="o">(</span><span class="n">j</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
            <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">Math</span><span class="o">.</span><span class="na">min</span><span class="o">(</span><span class="n">j</span> <span class="o">/</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">s</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span> <span class="n">k</span><span class="o">++)</span> <span class="o">{</span>
                <span class="c1">// 使用备份 dp 数组</span>
                <span class="c1">// 比较的二者前面为 dp，为的是既能最开始作为旧值比较大小，也能之后比较赋值最大值</span>
                <span class="c1">// 而如果前者也是 dpBackups，可能出现的情况：</span>
                <span class="c1">// 先，Math.max(1, 3)，显然，会令 dp[j] 为 3</span>
                <span class="c1">// 然后，Math.max(1, 2)，显然，会令 dp[j] 为2，就不是最大值了，</span>
                <span class="c1">// 我其实也不知道运行下来，会不会出现这种情况，保险起见</span>
                <span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">j</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">*</span> <span class="n">k</span> <span class="o">+</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">j</span> <span class="o">-</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">*</span> <span class="n">k</span><span class="o">]);</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

</details>

<ol start="2">
<li>改成使用分组的形式，分为 <code>v</code> 组，将原来的 <code>j</code> 循环进行拆分：</li>
</ol>
<details>

<p><summary>参考代码</summary></p>
<div class="highlight"><pre><span class="n">Integer</span><span class="o">[]</span> <span class="n">dpBackups</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">dpBackups</span> <span class="o">=</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">copyOf</span><span class="o">(</span><span class="n">dp</span><span class="o">,</span> <span class="n">dp</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
    <span class="c1">// 组次，取值范围 [0, w[i]-1] 或 [1, w[i]]</span>
    <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">r</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">r</span> <span class="o">&lt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">r</span><span class="o">++)</span> <span class="o">{</span>
        <span class="c1">// 从 r 开始，每次加 w[i], 组内循环</span>
        <span class="c1">// 要提醒的是，数组不是只能挨着读。</span>
        <span class="c1">// 合理使用 for 循环里的执行语句，不是只能 ++，合理使用可以简化循环内操作。</span>
        <span class="c1">// 这里如果是 k++, 用组内索引每次还要再计算</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">r</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;</span> <span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">k</span> <span class="o">+=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">k</span> <span class="o">&gt;=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
                <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">z</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">z</span> <span class="o">&lt;=</span> <span class="n">Math</span><span class="o">.</span><span class="na">min</span><span class="o">(</span><span class="n">k</span> <span class="o">/</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">s</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span> <span class="n">z</span><span class="o">++)</span> <span class="o">{</span>
                    <span class="c1">// 使用备份 dp 数组</span>
                    <span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">],</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">*</span> <span class="n">z</span> <span class="o">+</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">k</span> <span class="o">-</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">*</span> <span class="n">z</span><span class="o">]);</span>
                <span class="o">}</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

</details>

<ol start="3">
<li>尝试去掉最内层的 <code>for</code> 循环，使用单调队列，</li>
</ol>
<p>因为本身队列内存的就是索引，然后使用备份的 <code>dpBackups</code> 数组做操作，所以不需要在存储队列对应的索引。</p>
<details>

<p><summary> 参考代码 </summary></p>
<div class="highlight"><pre><span class="n">Integer</span><span class="o">[]</span> <span class="n">dpBackups</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>

<span class="n">Deque</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">queue</span> <span class="o">=</span> <span class="k">new</span> <span class="n">LinkedList</span><span class="o">&lt;&gt;();</span>

<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">dpBackups</span> <span class="o">=</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">copyOf</span><span class="o">(</span><span class="n">dp</span><span class="o">,</span> <span class="n">dp</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
    <span class="c1">// 分组</span>
    <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">head</span> <span class="o">=</span> <span class="mi">0</span><span class="o">,</span> <span class="n">tail</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
        <span class="c1">// 依次对每个组内访问</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">j</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">k</span> <span class="o">+=</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
            <span class="c1">// 队首不在窗口内，弹出</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">queue</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">queue</span><span class="o">.</span><span class="na">getFirst</span><span class="o">()</span> <span class="o">&lt;</span> <span class="n">k</span> <span class="o">-</span> <span class="n">s</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">*</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
                <span class="n">queue</span><span class="o">.</span><span class="na">poll</span><span class="o">();</span>
            <span class="o">}</span>

            <span class="c1">// 最大价值与 dpBackups[k] 小的，全部踢出</span>
            <span class="c1">// 因为每个元素最多进出一次，所以整个 k 的 for 循环内，</span>
            <span class="c1">// 这个 while 运行的次数，不会大于 k 这个组内元素个数，也就是不会影响到时间复杂度</span>
            <span class="k">while</span> <span class="o">(</span><span class="n">queue</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">k</span><span class="o">]</span> <span class="o">&gt;=</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">queue</span><span class="o">.</span><span class="na">getLast</span><span class="o">()]</span> <span class="o">+</span> <span class="o">(</span><span class="n">k</span><span class="o">-</span><span class="n">queue</span><span class="o">.</span><span class="na">getLast</span><span class="o">())</span> <span class="o">/</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">*</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="o">{</span>
                <span class="n">queue</span><span class="o">.</span><span class="na">pollLast</span><span class="o">();</span>
            <span class="o">}</span>
            <span class="c1">// 放入新值</span>
            <span class="n">queue</span><span class="o">.</span><span class="na">offerLast</span><span class="o">(</span><span class="n">k</span><span class="o">);</span>

            <span class="c1">// 赋值最大值</span>
            <span class="k">if</span><span class="o">(</span><span class="n">queue</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span><span class="o">){</span>
                <span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">],</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">queue</span><span class="o">.</span><span class="na">element</span><span class="o">()]</span> <span class="o">+</span> <span class="o">(</span><span class="n">k</span> <span class="o">-</span> <span class="n">queue</span><span class="o">.</span><span class="na">element</span><span class="o">())</span> <span class="o">/</span> <span class="n">w</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">*</span> <span class="n">c</span><span class="o">[</span><span class="n">i</span><span class="o">]);</span>
            <span class="o">}</span>
        <span class="o">}</span>
        <span class="c1">// 每组使用完，清空队列，给下一组用。</span>
        <span class="n">queue</span><span class="o">.</span><span class="na">clear</span><span class="o">();</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

</details>

<ol start="4">
<li>因为使用的单调队列，其实我们可以将后边的循环，直接放入前面输入的循环内，删去 <code>s, w ,c</code> 数组。</li>
</ol>
<details>

<p><summary>参考代码</summary></p>
<div class="highlight"><pre><span class="n">Integer</span><span class="o">[]</span> <span class="n">dpBackups</span><span class="o">;</span>
<span class="n">Deque</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">queue</span> <span class="o">=</span> <span class="k">new</span> <span class="n">LinkedList</span><span class="o">&lt;&gt;();</span>

<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">v</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
    <span class="n">c</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
    <span class="n">s</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>

    <span class="n">dpBackups</span> <span class="o">=</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">copyOf</span><span class="o">(</span><span class="n">dp</span><span class="o">,</span> <span class="n">dp</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
    <span class="c1">// 分组</span>
    <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">v</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">head</span> <span class="o">=</span> <span class="mi">0</span><span class="o">,</span> <span class="n">tail</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
        <span class="c1">// 依次对每个组内访问</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">j</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">k</span> <span class="o">+=</span> <span class="n">v</span><span class="o">)</span> <span class="o">{</span>
            <span class="c1">// 队首不在窗口内，弹出</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">queue</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">queue</span><span class="o">.</span><span class="na">getFirst</span><span class="o">()</span> <span class="o">&lt;</span> <span class="n">k</span> <span class="o">-</span> <span class="n">s</span> <span class="o">*</span> <span class="n">v</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">queue</span><span class="o">.</span><span class="na">poll</span><span class="o">();</span>
            <span class="o">}</span>

            <span class="c1">// 最大价值与 dpBackups[k] 小的，全部踢出</span>
            <span class="k">while</span> <span class="o">(</span><span class="n">queue</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">k</span><span class="o">]</span> <span class="o">&gt;=</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">queue</span><span class="o">.</span><span class="na">getLast</span><span class="o">()]</span> <span class="o">+</span> <span class="o">(</span><span class="n">k</span><span class="o">-</span><span class="n">queue</span><span class="o">.</span><span class="na">getLast</span><span class="o">())</span> <span class="o">/</span> <span class="n">v</span> <span class="o">*</span> <span class="n">c</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">queue</span><span class="o">.</span><span class="na">pollLast</span><span class="o">();</span>
            <span class="o">}</span>
            <span class="c1">// 放入新值</span>
            <span class="n">queue</span><span class="o">.</span><span class="na">offerLast</span><span class="o">(</span><span class="n">k</span><span class="o">);</span>

            <span class="c1">// 赋值最大值</span>
            <span class="k">if</span><span class="o">(</span><span class="n">queue</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span><span class="o">){</span>
             <span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">],</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">queue</span><span class="o">.</span><span class="na">element</span><span class="o">()]</span> <span class="o">+</span> <span class="o">(</span><span class="n">k</span> <span class="o">-</span> <span class="n">queue</span><span class="o">.</span><span class="na">element</span><span class="o">())</span> <span class="o">/</span> <span class="n">v</span> <span class="o">*</span> <span class="n">c</span><span class="o">);</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

</details>

<ul>
<li>对应指针代码</li>
</ul>
<details>

<p><summary>参考代码</summary></p>
<div class="highlight"><pre><span class="kt">int</span><span class="o">[]</span> <span class="n">queue</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">capacity</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
    <span class="n">v</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
    <span class="n">c</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
    <span class="n">s</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>

    <span class="n">dpBackups</span> <span class="o">=</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">copyOf</span><span class="o">(</span><span class="n">dp</span><span class="o">,</span> <span class="n">dp</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
    <span class="c1">// 分组</span>
    <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">v</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
        <span class="kt">int</span> <span class="n">head</span> <span class="o">=</span> <span class="mi">0</span><span class="o">,</span> <span class="n">tail</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="o">;</span>
        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">j</span><span class="o">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">capacity</span><span class="o">;</span> <span class="n">k</span> <span class="o">+=</span> <span class="n">v</span><span class="o">)</span> <span class="o">{</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">head</span> <span class="o">&lt;=</span> <span class="n">tail</span> <span class="o">&amp;&amp;</span> <span class="n">queue</span><span class="o">[</span><span class="n">head</span><span class="o">]</span> <span class="o">&lt;</span> <span class="n">k</span> <span class="o">-</span> <span class="n">s</span> <span class="o">*</span> <span class="n">v</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">head</span><span class="o">++;</span>
            <span class="o">}</span>
            <span class="k">while</span> <span class="o">(</span><span class="n">head</span> <span class="o">&lt;=</span> <span class="n">tail</span> <span class="o">&amp;&amp;</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">k</span><span class="o">]</span> <span class="o">&gt;=</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">queue</span><span class="o">[</span><span class="n">tail</span><span class="o">]]</span> <span class="o">+</span> <span class="o">(</span><span class="n">k</span> <span class="o">-</span> <span class="n">queue</span><span class="o">[</span><span class="n">tail</span><span class="o">])</span> <span class="o">/</span> <span class="n">v</span> <span class="o">*</span> <span class="n">c</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">tail</span><span class="o">--;</span>
            <span class="o">}</span>
            <span class="n">queue</span><span class="o">[++</span><span class="n">tail</span><span class="o">]</span> <span class="o">=</span> <span class="n">k</span><span class="o">;</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">head</span> <span class="o">&lt;=</span> <span class="n">tail</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">dp</span><span class="o">[</span><span class="n">k</span><span class="o">],</span> <span class="n">dpBackups</span><span class="o">[</span><span class="n">queue</span><span class="o">[</span><span class="n">head</span><span class="o">]]</span> <span class="o">+</span> <span class="o">(</span><span class="n">k</span> <span class="o">-</span> <span class="n">queue</span><span class="o">[</span><span class="n">head</span><span class="o">])</span> <span class="o">/</span> <span class="n">v</span> <span class="o">*</span> <span class="n">c</span><span class="o">);</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

</details>

<p>时间复杂度: $O(V * n)$</p>
<h2 id="_47">四、混合三种背包问题<a class="headerlink" href="#_47" title="Permanent link"></a></h2>
<h3 id="_48">介绍<a class="headerlink" href="#_48" title="Permanent link"></a></h3>
<p>将前面三种简单的问题叠加成较复杂的问题。</p>
<h3 id="_49">问题描述<a class="headerlink" href="#_49" title="Permanent link"></a></h3>
<p>将前三者混合起来，也就是有的物品只可以取一次(01背包)，有的物品可以取无限次(完全背包)，有的物品可以取的次数有限(多重背包)。应该怎么办？</p>
<h3 id="01_2">01背包与完全背包的混合<a class="headerlink" href="#01_2" title="Permanent link"></a></h3>
<p>我们已知二者代码上只有一处不同，就是在 <code>j</code> 的 <code>for</code> 循环上，我们只需根据物品的类别进行判断就可。复杂度为 O(VN)，V为容量N为数量</p>
<p>伪代码：</p>
<div class="highlight"><pre>for i=1..n
  if i件物品属于01背包
    for j=capacity..1
      dp[j]=max(dp[j], dp[j-w[i]])
  if i件物品属于完全背包
    for j=1..capacity
      dp[j]=max(dp[j], dp[j-w[i]])
</pre></div>

<h3 id="_50">再加上多重背包<a class="headerlink" href="#_50" title="Permanent link"></a></h3>
<blockquote>
<p>来自: <a href="https://www.cnblogs.com/coded-ream/p/7208019.html">背包问题（背包九讲）</a></p>
<p>如果再加上有的物品最多可以取有限次，那么原则上也可以给出 O (VN) 的解法：遇到多重背包类型的物品用<a href="#单调队列">单调队列</a>解即可。</p>
<blockquote>
<p><a href="https://www.cnblogs.com/coded-ream/p/7208019.html">背包问题（背包九讲）</a>中</p>
<p>多重背包一节下的 O (VN) 的算法，中说明：</p>
<p>多重背包问题同样有 O (VN) 的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊 O (1) 的时间求解。由于用单调队列优化的 DP 已超出了 NOIP 的范围，故本文不再展开讲解。我最初了解到这个方法是在楼天成的 “男人八题” 幻灯片 上。</p>
<blockquote>
<p>NOIP: <a href="https://new.qq.com/omn/20210427/20210427A01RT000.html">一文了解 CSP、NOIP、NOI 三大信息学赛事</a></p>
<p>NOIP 为全国青少年信息学奥林匹克联赛，每年由中国计算机学会统一组织。NOIP 在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。</p>
<p>自 2020 年起，NOIP 仅面向高中学生参加，参赛人数仅限一万人。值得注意的是，NOIP 是参加 NOI 的必要条件，不参加 NOIP 将不具有参加 NOI 的资格。此外，NOIP 明确了 2022 年后将不可使用其他编程语言，只能使用 C++ 语言。
</p>
</blockquote>
</blockquote>
<p>但如果不考虑超过 NOIP 范围的算法的话，用 P03 中将每个这类物品分成 O (log n [i]) 个 01 背包的物品的方法也已经很优了。</p>
<p>当然，更清晰的写法是调用我们前面给出的三个相关过程。</p>
<div class="highlight"><pre>for i=1..N
    if 第i件物品属于01背包
        ZeroOnePack(c[i],w[i])
    else if 第i件物品属于完全背包
        CompletePack(c[i],w[i])
    else if 第i件物品属于多重背包
        MultiplePack(c[i],w[i],n[i])
</pre></div>

<p>在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现了编程中抽象的威力。如果你一直就是以这种 “抽象出过程” 的方式写每一类背包问题的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法，对吗？</p>
<p><strong>小结</strong></p>
<p>在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现了编程中抽象的威力。如果你一直就是以这种 “抽象出过程” 的方式写每一类背包问题的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法，对吗？</p>
</blockquote>
<p>就是说，对属于不同背包的第 <code>i</code> 件物品，使用各自的代码就好了。</p>
<h2 id="_51">五、二维费用的背包问题<a class="headerlink" href="#_51" title="Permanent link"></a></h2>
<h3 id="_52">介绍<a class="headerlink" href="#_52" title="Permanent link"></a></h3>
<p>一个简单的常见扩展。</p>
<h3 id="_53">问题描述<a class="headerlink" href="#_53" title="Permanent link"></a></h3>
<p>有 N 件物品和一个容量时 V 的背包（条件1），背包能承受的最大重量是 M （条件2）。</p>
<p>每件物品只能用一次，体积是 ai，重量是 bi，价值是 Wi。</p>
<p>求解将那些物品装入背包，可是=使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量（必须同时满足两种要求），且价值总和最大。</p>
<p>输出最大价值。</p>
<blockquote>
<p>前面我把容量和重量混着用的，但是到这里就不一样了，不一样的概念了</p>
</blockquote>
<h3 id="_54">思路<a class="headerlink" href="#_54" title="Permanent link"></a></h3>
<p>这里是二维费用，开始我们类似01背包的二维数组，这里先使用三维数组。那么对比01背包。</p>
<p>最大价值应该是</p>
<p><code>dp[i][j][k] = max(dp[i-1][j][k], dp[i-1] [j-a[i]] [k-b[i]] + w[i])</code></p>
<p>二维应该是</p>
<p><code>dp[j][k] = max(dp[j][k], dp[j-a[i]][k-b[]</code></p>
<h3 id="_55"><a class="headerlink" href="#_55" title="Permanent link"></a></h3>
<h2 id="_56">六、分组的背包问题<a class="headerlink" href="#_56" title="Permanent link"></a></h2>
<h3 id="_57">介绍<a class="headerlink" href="#_57" title="Permanent link"></a></h3>
<p>一种题目类型，也是一个有用的模型。后两节的基础。</p>
<h2 id="_58">七、有依赖的背包问题<a class="headerlink" href="#_58" title="Permanent link"></a></h2>
<h3 id="_59">介绍<a class="headerlink" href="#_59" title="Permanent link"></a></h3>
<p>另一种给物品的选取加上限制的方法。</p>
<h2 id="_60">八、泛化物品<a class="headerlink" href="#_60" title="Permanent link"></a></h2>
<h3 id="_61">介绍<a class="headerlink" href="#_61" title="Permanent link"></a></h3>
<p>dd 大神关于背包问题的思考成果，有一点抽象。</p>
<h2 id="_62">九、背包问题问法的变化<a class="headerlink" href="#_62" title="Permanent link"></a></h2>
<h3 id="_63">介绍<a class="headerlink" href="#_63" title="Permanent link"></a></h3>
<p>试图触类旁通、举一反三。</p>
<h2 id="_64">其他知识点附加<a class="headerlink" href="#_64" title="Permanent link"></a></h2>
<h3 id="_65">单调队列<a class="headerlink" href="#_65" title="Permanent link"></a></h3>
<h4 id="_66">相关资源<a class="headerlink" href="#_66" title="Permanent link"></a></h4>
<ul>
<li><a href="https://blog.csdn.net/LJD201724114126/article/details/80663855">单调队列详解</a></li>
<li><a href="https://www.cnblogs.com/ljy-endl/p/11638389.html">单调队列优化 DP（超详细！！！）</a></li>
<li><a href="https://zhuanlan.zhihu.com/p/346354943">算法学习笔记 (66): 单调队列</a></li>
</ul>
<p>建议看这个↓，这个好：</p>
<ul>
<li><a href="https://www.bilibili.com/video/BV1rb411S7eB">单调队列 算法详解与模板题代码实现</a></li>
</ul>
<h4 id="_67">前置要点<a class="headerlink" href="#_67" title="Permanent link"></a></h4>
<ol>
<li>首先，要提一下平常代码中，很常见的范围问题，然后才能继续说单调队列。</li>
</ol>
<p>也就是范围，算前不算后，例如</p>
<ul>
<li>
<p><code>java</code> 中，使用 <code>substring</code> 获取规定索引范围内的字符串</p>
<div class="highlight"><pre><span class="n">String</span> <span class="n">s</span> <span class="o">=</span> <span class="s">&quot;0123456789&quot;</span><span class="o">;</span>
<span class="n">String</span> <span class="n">subStr</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="na">substring</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">3</span><span class="o">);</span> <span class="c1">// substring(int beginIndex, int endIndex)</span>
</pre></div>

<p>结果得到的字符串就是 <code>12</code></p>
<p>也就是前面索引的值会包含在内，但后边不会，这点看源码注释也能知道 ：</p>
<div class="highlight"><pre>@param   beginIndex   the beginning index, inclusive.
@param   endIndex     the ending index, exclusive.
</pre></div>

</li>
</ul>
<ol start="2">
<li>什么是队列</li>
</ol>
<p>一种特殊的线性表，它只允许在表的前端进行删除操作，在表的后端进行插入操作。</p>
<h4 id="_68">介绍<a class="headerlink" href="#_68" title="Permanent link"></a></h4>
<p><strong>说明</strong></p>
<ul>
<li>
<p>单调队列，又叫 Monotone Priority Queue</p>
</li>
<li>
<p>从名字可以看出，单调队列是一个 优先队列（Priority Queue）</p>
<p>优先队列: 优先级高的元素进队时可以插队</p>
</li>
<li>
<p>单调队列</p>
<ul>
<li>
<p>队列始终满足从队首开始，优先级递减，（与优先队列一样）</p>
</li>
<li>
<p>进队时间在队列中越靠后就是越晚。（与普通队列一样）</p>
</li>
<li>
<p>假如后进的优先级靠前，往前插入或者原地不动都无法同时满足前面两条，我们需要：</p>
</li>
</ul>
<p>新元素进队时，将前面优先级低于自己的直接踢出队。</p>
</li>
<li>
<details>

</li>
</ul>
<p><summary>单调队列为双端队列</summary></p>
<ul>
<li>
<details>

<p><summary>为什么不能是单端队列？</summary></p>
<ol>
<li>因为单端队列不能保证队列的单调性，或者说在只能进出一次的情况下，保证队列的单调性。</li>
</ol>
<p>就不能保证队首一直为最大（最小值）</p>
<p>例如求最小值，进入顺序为 2 6 3 8</p>
<p>因为只进出一次，后边进的只能判断队首的大小，对队尾没有办法比较与操作，</p>
<p>假如没有队列满弹出队首情况，每次都做 <code>while</code> 将前面比队尾大的都弹出，可以保证队首最小。</p>
<p>但是假如现在，窗口只有 3 ，我们需要将 2 弹出，这时，最小的 3 在队列的中间，而不是队首，就出错了。</p>
<ol start="2">
<li>前面说了，优先级递减，我们需要，新元素进队时，将前面优先级低于自己的直接踢出队。</li>
</ol>
<p>保证自己是最晚的，且优先级最小，所以就要对队尾进行操作。</p>
<p>单端队列是做不到的。</p>
</details>

</li>
<li>
<details>

<p><summary>为什么是双端队列</summary></p>
<p>前面说了保证满足优先队列与普通队列的方法：新元素进队时，将前面优先级低于自己的直接踢出队。</p>
<p>就需要对队尾进行操作。而不是对队首操作。</p>
</details>

</li>
</ul>
</details>

<p><strong>用途</strong></p>
<p>单调队列是一种主要用于解决滑动窗口 类问题的数据结构，即，在长度为 n 的序列中，求每个长度为 m 的区间的区间最值。</p>
<p>一般用于</p>
<ol>
<li>
<p>动态规划中，优化 dp </p>
</li>
<li>
<p>用于动态维护数组的最值（最大或最小）</p>
</li>
</ol>
<h5 id="_69">单调队列的实现<a class="headerlink" href="#_69" title="Permanent link"></a></h5>
<blockquote>
<p>前面的介绍的说明里已经说了，我们需要：新元素进队时，将前面优先级低于自己的直接踢出队。</p>
<p>所以实现方法如下：</p>
</blockquote>
<ol>
<li>当有新元素要进队，先不断的与队尾比较，将所有的比自己优先级小的踢出（求最大(小)值，当然是值越大(小)优先级越高）。</li>
</ol>
<blockquote>
<p>保证队列内 优先级递减，且越靠后的进队时间越晚</p>
</blockquote>
<ol start="2">
<li>对队首的最值，判断是否还在窗口内，如果出了窗口，弹出队首元素。</li>
</ol>
<blockquote>
<p>因为元素会从队尾踢出，不能单纯的从队列长度判断队首是否还位于窗口内。</p>
<p>并且不知道踢出后下一个元素在原来的什么位置，所以我们要对每个元素所在位置存储。</p>
</blockquote>
<ol start="3">
<li>
<p>新元素加入队尾</p>
</li>
<li>
<p>按要求输出队首元素(最大或最小值)</p>
</li>
</ol>
<blockquote>
<p>其中第 1, 2 步可以互换，1，3 步不行，2, 3 步，大概也行。</p>
</blockquote>
<details>

<summary>参考代码（求连续m个数字的最小值）</summary>

<div class="highlight"><pre><span class="kn">package</span> <span class="nn">sing</span><span class="o">;</span>

<span class="kn">import</span> <span class="nn">java.util.*</span><span class="o">;</span>

<span class="cm">/**</span>
<span class="cm"> - @author xing</span>
<span class="cm"> - @date 2022/2/27 14:09</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Main</span> <span class="o">{</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Scanner</span> <span class="n">sc</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Scanner</span><span class="o">(</span><span class="n">System</span><span class="o">.</span><span class="na">in</span><span class="o">);</span>

        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>

        <span class="c1">// 声明单调队列</span>
        <span class="n">Deque</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">deque</span> <span class="o">=</span> <span class="k">new</span> <span class="n">LinkedList</span><span class="o">&lt;&gt;();</span>
        <span class="c1">// 声明存储对应索引队列</span>
        <span class="n">Deque</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">indexDeque</span> <span class="o">=</span> <span class="k">new</span> <span class="n">LinkedList</span><span class="o">&lt;&gt;();</span>

        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="kt">int</span> <span class="n">number</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>

            <span class="c1">// 所有队尾优先级低于新进值的，全部踢出</span>
            <span class="k">while</span> <span class="o">(</span><span class="n">deque</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">deque</span><span class="o">.</span><span class="na">getLast</span><span class="o">()</span> <span class="o">&gt;</span> <span class="n">number</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">deque</span><span class="o">.</span><span class="na">pollLast</span><span class="o">();</span>
                <span class="c1">// 索引队列保持统一操作</span>
                <span class="n">indexDeque</span><span class="o">.</span><span class="na">pollLast</span><span class="o">();</span>
            <span class="o">}</span>

            <span class="c1">// 判断队首是否在窗口内</span>
            <span class="c1">// 要连续的窗口值内最大值，要把 i 包括在内</span>
            <span class="c1">// 例如队首索引为 1， 窗口为 2，现在 i 为 3，那么就是要 2，3，索引为 1 的就要踢出</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">indexDeque</span><span class="o">.</span><span class="na">size</span><span class="o">()</span> <span class="o">!=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">indexDeque</span><span class="o">.</span><span class="na">getFirst</span><span class="o">()</span> <span class="o">+</span> <span class="n">m</span> <span class="o">&lt;=</span> <span class="n">i</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">indexDeque</span><span class="o">.</span><span class="na">pollFirst</span><span class="o">();</span>
                <span class="n">deque</span><span class="o">.</span><span class="na">pollFirst</span><span class="o">();</span>
            <span class="o">}</span>

            <span class="c1">// 放入新值</span>
            <span class="n">deque</span><span class="o">.</span><span class="na">offerLast</span><span class="o">(</span><span class="n">number</span><span class="o">);</span>
            <span class="n">indexDeque</span><span class="o">.</span><span class="na">offerLast</span><span class="o">(</span><span class="n">i</span><span class="o">);</span>

            <span class="c1">// 打印最值，&gt;= m - 1 因为索引从 0 开始， m - 1 的时候已经有 m 个连续的数了</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">i</span> <span class="o">&gt;=</span> <span class="n">m</span> <span class="o">-</span> <span class="mi">1</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">deque</span><span class="o">.</span><span class="na">getFirst</span><span class="o">());</span>
            <span class="o">}</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

其中，对队首是否在窗口内的判断，可以放在放入新值之后。

因为没有对队列长度的限制，这里先放入，再踢出窗口外的值也是可以的。

</details>

<details>

<summary>指针版本参考代码</summary>

<div class="highlight"><pre><span class="kn">package</span> <span class="nn">sing</span><span class="o">;</span>

<span class="kn">import</span> <span class="nn">java.util.*</span><span class="o">;</span>

<span class="cm">/**</span>
<span class="cm"> * @author xing</span>
<span class="cm"> * @date 2022/2/27 14:09</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kd">class</span> <span class="nc">Main</span> <span class="o">{</span>

    <span class="kd">public</span> <span class="kd">static</span> <span class="kt">void</span> <span class="nf">main</span><span class="o">(</span><span class="n">String</span><span class="o">[]</span> <span class="n">args</span><span class="o">)</span> <span class="o">{</span>
        <span class="n">Scanner</span> <span class="n">sc</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Scanner</span><span class="o">(</span><span class="n">System</span><span class="o">.</span><span class="na">in</span><span class="o">);</span>

        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>
        <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>

        <span class="c1">// 声明单调队列</span>
        <span class="n">Deque</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">deque</span> <span class="o">=</span> <span class="k">new</span> <span class="n">LinkedList</span><span class="o">&lt;&gt;();</span>
        <span class="c1">// 声明存储对应索引队列</span>
        <span class="n">Deque</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">indexDeque</span> <span class="o">=</span> <span class="k">new</span> <span class="n">LinkedList</span><span class="o">&lt;&gt;();</span>

        <span class="n">Integer</span><span class="o">[]</span> <span class="n">dequeArray</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>
        <span class="n">Integer</span><span class="o">[]</span> <span class="n">indexDequeArray</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>

        <span class="c1">// 定义头部与尾部，并且初始化时令 tail &lt; head，代表队列为空（ head=tail 代表有一个元素）</span>
        <span class="kt">int</span> <span class="n">head</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="kt">int</span> <span class="n">tail</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>

        <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
            <span class="kt">int</span> <span class="n">number</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">nextInt</span><span class="o">();</span>

            <span class="c1">// 所有队尾优先级低于新进值的，全部踢出</span>
            <span class="k">while</span> <span class="o">(</span><span class="n">tail</span> <span class="o">&gt;=</span> <span class="n">head</span> <span class="o">&amp;&amp;</span> <span class="n">dequeArray</span><span class="o">[</span><span class="n">tail</span><span class="o">]</span> <span class="o">&gt;</span> <span class="n">number</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">tail</span><span class="o">--;</span>
            <span class="o">}</span>

            <span class="c1">// 判断队首是否在窗口内</span>
            <span class="c1">// 要连续的窗口值内最大值，要把 i 包括在内</span>
            <span class="c1">// 例如队首索引为 1， 窗口为 2，现在 i 为 3，那么就是要 2，3，索引为 1 的就要踢出</span>
            <span class="k">if</span> <span class="o">(</span><span class="n">tail</span> <span class="o">&gt;=</span> <span class="n">head</span> <span class="o">&amp;&amp;</span> <span class="n">indexDequeArray</span><span class="o">[</span><span class="n">head</span><span class="o">]</span> <span class="o">+</span> <span class="n">m</span> <span class="o">&lt;=</span> <span class="n">i</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">head</span><span class="o">++;</span>
            <span class="o">}</span>

            <span class="c1">// 要放入新值，尾部指针往后移</span>
            <span class="n">tail</span> <span class="o">++;</span>

            <span class="c1">// 放入新值</span>
            <span class="n">dequeArray</span><span class="o">[</span><span class="n">tail</span><span class="o">]</span> <span class="o">=</span> <span class="n">number</span><span class="o">;</span>
            <span class="n">indexDequeArray</span><span class="o">[</span><span class="n">tail</span><span class="o">]=</span><span class="n">i</span><span class="o">;</span>

            <span class="c1">// 打印最值，&gt;= m - 1 因为索引从 0 开始， m - 1 的时候已经有 m 个连续的数了</span>
            <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">dequeArray</span><span class="o">[</span><span class="n">head</span><span class="o">]);</span>
        <span class="o">}</span>
    <span class="o">}</span>
<span class="o">}</span>
</pre></div>

其中，对队首是否在窗口内的判断，可以放在放入新值之后。

因为定义的队列数组长度还是够长的，这里先放入，再踢出窗口外的值也是可以的。

注意这里队列长度定义是 n 而不是 窗口大小 m，因为用指针不断移动，这样原来的值不用变。

如果一直用一个 m 的数组，要不断更新里边内容，不好。

除非真的特别大，再另说吧。那我也不造啊。

</details>

<h4 id="_70">例题<a class="headerlink" href="#_70" title="Permanent link"></a></h4>
<h5 id="m">一 求 m 区间内的最小值<a class="headerlink" href="#m" title="Permanent link"></a></h5>
<blockquote>
<p>来源: <a href="https://www.cnblogs.com/ljy-endl/p/11638389.html">单调队列优化 DP（超详细！！！）</a></p>
<p><a href="https://www.luogu.com.cn/problem/P1440">洛谷_P1440</a></p>
</blockquote>
<p>一个含有 n 项的数列 (n&lt;=2000000)，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 m 项则从第 1 个数开始，若前面没有数则输出 0。</p>
<p>输入格式</p>
<p>第一行两个数 n，m。 第二行，n 个正整数，为所给定的数列。</p>
<p>输出格式</p>
<p>n 行，第 i 行的一个数 ai，为所求序列中第 i 个数前 m 个数的最小值。</p>
<p><strong>输入</strong></p>
<p>```:no-line-numbers
6 2
7 8 1 4 3 2
<div class="highlight"><pre>**输出**

```:no-line-numbers
0 7 7 1 1 3
````


&gt; 几种解题思路(来自[单调队列优化 DP（超详细！！！）][单调队列优化 DP（超详细！！！）])：
&gt; 
&gt; 1、暴力枚举以 i-1 为结尾的前 m 个数。时间 O (n*m)，T T T.
&gt; 
&gt; 2、rmq 求解 O (nlog n) 貌似会 T
&gt; 
&gt; 3、线段树求解 O (nlog n) 当 n=1e7 时也超时，空间，代码量大 需要更优的 O (n) 的解法处理。
&gt; 
&gt; 4、单调队列来了 因为每一个答案只与当前下标的前 m 个有关，所以可以用单调队列维护前 m 个的最小值， 　

- &lt;details&gt;

  &lt;summary&gt;参考代码&lt;/summary&gt;

  ```java
  package sing;

  import java.util.*;

  /**
   - @author xing
   - @date 2022/2/27 14:09
   */
  public class Main {

      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);

          int n = sc.nextInt();
          int m = sc.nextInt();

          // 声明单调队列
          Deque&lt;Integer&gt; deque = new LinkedList&lt;&gt;();
          // 声明存储对应下标的
          Deque&lt;Integer&gt; indexDeque = new LinkedList&lt;&gt;();

          for (int i = 0; i &lt; n; i++) {
              int number = sc.nextInt();

              // 前面没有数
              if(i == 0) {
                  // 输出 0
                  System.out.println(0);
              }

              // 队列不为空
              if (deque.size() != 0) {
                  // 输出（上一个循环得到的）最值
                  // 因为求得是前面 m 个值，所以关于新输入的值的处理放在后边
                  System.out.println(deque.getFirst());
              }

              // 对新输入的值，进行相关操作
              // 将队尾所有比新输入的 number 大的都踢出
              while (deque.size() != 0 &amp;&amp; deque.getLast() &gt; number) {
                  deque.pollLast();
                  // 索引队列做相同操作，确保对应关系
                  indexDeque.pollLast();
              }

              // 判断队首是否在窗口内
              // 例如 队首索引为 1, 窗口大小为 2，i 为 3，代表新加入的是索引为 3 的值，
              // 并且这里是为下一个循环到 i 为 4 做准备，窗口应该是 2, 3，就要吧索引为 1 的踢出
              if (indexDeque.size() != 0 &amp;&amp; indexDeque.getFirst() + m &lt;= i) {
                  deque.pollFirst();
                  indexDeque.pollFirst();
              }

              // 添加新元素
              deque.offerLast(number);
              // 对应添加索引
              indexDeque.offerLast(i);
          }
      }

  }
  ```

  &lt;/details&gt;


- 如果是求所有连续 `m` 个数字的最值，其实范围也一样：

  &lt;details&gt;

  &lt;summary&gt;参考代码&lt;/summary&gt;

  ```java
  package sing;

  import java.util.*;

  /**
   - @author xing
   - @date 2022/2/27 14:09
   */
  public class Main {

      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);

          int n = sc.nextInt();
          int m = sc.nextInt();

          // 声明单调队列
          Deque&lt;Integer&gt; deque = new LinkedList&lt;&gt;();
          // 声明存储对应索引队列
          Deque&lt;Integer&gt; indexDeque = new LinkedList&lt;&gt;();

          for (int i = 0; i &lt; n; i++) {
              int number = sc.nextInt();

              // 所有队尾优先级低于新进值的，全部踢出
              while (deque.size() != 0 &amp;&amp; deque.getLast() &gt; number) {
                  deque.pollLast();
                  // 索引队列保持统一操作
                  indexDeque.pollLast();
              }

              // 判断队首是否在窗口内
              // 要连续的窗口值内最大值，要把 i 包括在内
              // 例如队首索引为 1， 窗口为 2，现在 i 为 3，那么就是要 2，3，索引为 1 的就要踢出
              if (indexDeque.size() != 0 &amp;&amp; indexDeque.getFirst() + m &lt;= i) {
                  indexDeque.pollFirst();
                  deque.pollFirst();
              }

              // 放入新值
              deque.offerLast(number);
              indexDeque.offerLast(i);

              // 打印最值，&gt;= m - 1 因为索引从 0 开始， m - 1 的时候已经有 m 个连续的数了
              if (i &gt;= m - 1) {
                  System.out.println(deque.getFirst());
              }
          }
      }
  }
  ```

  输出:

  ```:no-line-numbers
  7 1 1 3 2
  ```

  &lt;/details&gt;

- 如果是，不足窗口值的从第一位开始，去掉上一个最后判断的 `if` 就好了。因为队列首部始终是最大值。

  &lt;details&gt;

  输出: 

  ```:no-line-numbers
  7 7 1 1 3 2
  ```

  &lt;/details&gt;

##### 二 修剪草坪（不会）

&gt; 来源: [单调队列优化 DP（超详细！！！）][单调队列优化 DP（超详细！！！）]
&gt; 
&gt; [信息学奥赛一本通_1599][信息学奥赛一本通_1599]

**题目描述**

原题来自：USACO 2011 Open Gold

在一年前赢得了小镇的最佳草坪比赛后，FJ 变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ 希望能够再次夺冠。

然而，FJ 的草坪非常脏乱，因此，FJ 只能够让他的奶牛来完成这项工作。FJ 有 N 只排成一排的奶牛，编号为 1 到 N。每只奶牛的效率是不同的，奶牛 i 的效率为 Ei 。

靠近的奶牛们很熟悉，如果 FJ 安排超过 K 只连续的奶牛，那么这些奶牛就会罢工去开派对。因此，现在 FJ 需要你的帮助，计算 FJ 可以得到的最大效率，并且该方案中没有连续的超过 K 只奶牛。

**输入**

第一行：空格隔开的两个整数 N 和 K；

第二到 N+1 行：第 i+1 行有一个整数 Ei 。

**输出**

一行一个值，表示 FJ 可以得到的最大的效率值。

**输入样例**

```:no-line-numbers
5 2
1
2
3
4
5
</pre></div></p>
<p><strong>输出样例</strong></p>
<p><code>:no-line-numbers
12</code></p>
<p><strong>提示</strong></p>
<p>FJ 有 5 只奶牛，他们的效率为 1,2,3,4,5。他们希望选取效率总和最大的奶牛，但是他不能选取超过 2 只连续的奶牛。FJ 选择出了第三只以外的其他奶牛，总的效率为 1+2+4+5=12。</p>
<p>数据范围与提示：</p>
<p>对于全部数据，1≤N≤105,0≤Ei≤109 。</p>
<p><strong>参考代码</strong></p></article></body></html>